Efficiently search sorted arrays and binary search on the answer space.
Binary search halves the search space in each step, achieving O(log n). Beyond sorted arrays, it applies to rotated arrays, peak finding, and "binary search on the answer" where you search the result range instead of an index.
O(log n) per search
O(1) iterative, O(log n) recursive
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this when searching a sorted array and you want to keep a precise meaning for the current search space
At every step, the target must lie inside [left, right] if it exists at all. Binary search works because each comparison cuts that valid region roughly in half.
Problem Binary Search. Compare nums[mid] with the target, then discard the half that cannot possibly contain the answer.
// Classic binary search — sorted array
function search(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Use this when duplicates exist and you do not want just any match, but specifically the first or last valid index
The trick is to keep searching even after you find the target. Move left for the first occurrence and right for the last occurrence.
Problem Find First and Last Position of Element in Sorted Array. Run two binary searches, one biased left and one biased right.
// First/last occurrence — biased binary search
function searchRange(nums, target) {
function findFirst() {
let left = 0, right = nums.length - 1, ans = -1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) { ans = mid; right = mid - 1; }
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return ans;
}
function findLast() {
let left = 0, right = nums.length - 1, ans = -1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) { ans = mid; left = mid + 1; }
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return ans;
}
return [findFirst(), findLast()];
}Use this when the array itself is not directly being searched, but the answer lies in a numeric range and you can test whether a candidate answer is feasible
The key requirement is monotonicity: once a candidate becomes feasible, all larger or smaller candidates on one side must stay feasible. This is a very common interview pattern.
Problem Koko Eating Bananas. Guess an eating speed, check if all piles can be finished in time, and binary search the minimum feasible speed.
// Binary search on answer — Koko Eating Bananas
function minEatingSpeed(piles, h) {
let left = 1, right = Math.max(...piles);
const canFinish = speed =>
piles.reduce((hours, pile) => hours + Math.ceil(pile / speed), 0) <= h;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
if (canFinish(mid)) right = mid;
else left = mid + 1;
}
return left;
}Use this when a sorted array has been rotated, so normal sorted-order reasoning does not apply globally
In every step, at least one half is still sorted, and that half can be used to decide where the target may lie. The key is identifying which half remains ordered.
Problem Search in Rotated Sorted Array. Check whether the left half or right half is sorted, then decide whether the target belongs there.
// Rotated sorted array — identify sorted half
function searchRotated(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[left] <= nums[mid]) { // left half sorted
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else { // right half sorted
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}Use this when the problem asks for a local optimum, boundary transition, or minimum in a special monotonic structure
You may not be searching for exact equality, but for the first place where a property changes. In these cases, the decision rule comes from neighboring values instead of direct target comparison.
Problem Find Peak Element. If nums[mid] < nums[mid + 1], the peak must be on the right; otherwise it lies on the left side including mid.
// Peak/boundary — Find Peak Element
function findPeakElement(nums) {
let left = 0, right = nums.length - 1;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] < nums[mid + 1]) left = mid + 1; // peak is to the right
else right = mid; // peak is at mid or to the left
}
return left;
}Use this to avoid off-by-one mistakes
Binary search errors usually come from mixing loop conditions, interval meanings, and update rules from different templates. Pick one template and stay consistent with it from start to finish.
Problem Lower Bound Search. If you use a closed interval [left, right], then your loop is while (left <= right) and your updates must always shrink that same interval correctly.
// Template discipline — lower bound (first index >= target)
function lowerBound(nums, target) {
let left = 0, right = nums.length, ans = nums.length;
while (left < right) { // half-open [left, right)
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] >= target) { ans = mid; right = mid; }
else left = mid + 1;
}
return ans;
}