Binary search
AlgorithmsHigh priority~1.5 hHalve a sorted (or monotonic) search space each step — O(log n), if you get the invariant right.
Definition
Binary search discards half the search space each step, finding a target — or a boundary — in O(log n). It works whenever the space is monotonic: the values are sorted, or some yes/no predicate flips from false to true exactly once across the range. Each step inspects the midpoint, decides which half can't contain the answer, and throws it away.
The whole subtlety lives in the loop invariant: which half is safe to drop, whether the loop is lo <= hi or lo < hi, and whether mid becomes mid - 1, mid + 1, or stays put. Get the invariant precise and the off-by-one bugs disappear.
When to use
Reach for it on sorted data, and — less obviously — to binary-search the answer on any monotonic predicate: the smallest capacity that works, the maximum cut height that still yields enough, the rotation point. The recognition cue is a question you can phrase as “what is the boundary where feasible flips to infeasible?” — or simply an O(log n) requirement on an ordered input. If a linear scan would re-examine a range you've already ruled out, halving applies.
Techniques
Exact-match search — the textbook form. Use lo <= hi; on a hit, return mid; otherwise move lo = mid + 1 or hi = mid - 1. Returns the index or a not-found sentinel (search a sorted array).
Boundary / lower-bound search — instead of an exact value, find the first index where a predicate becomes true (the first element >= target, the first true in a boolean run). Use lo < hi with hi = mid (never mid - 1), so lo converges on the boundary. This is the most reusable shape — insertion index, first and last occurrence.
Binary search on the answer — when the input isn't sorted but the answer lives in a numeric range with a monotonic feasibility test, search that range directly: guess a value, check feasibility in O(n), and halve (cutting wood, minimum eating speed).
Search on a rotated / unsorted-but-structured array — the array isn't globally sorted, but at every midpoint one half still is. Detect the sorted half, decide whether the target lies inside its range, and recurse into the right half (rotated sorted array, find peak element).
Related structures
Binary search and its neighbors
Binary search is the search counterpart of sorting — sorting is what makes an array binary-searchable, and many problems pay an O(n log n) sort up front precisely to unlock O(log n) lookups afterward. It also rhymes with the two-pointers family: both collapse a range from its ends, but two pointers move linearly on a fixed comparison, while binary search jumps to the midpoint and discards half at once. When a problem says “monotonic” or “sorted” and asks for O(log n), binary search is the tool; when it asks for a pair or partition in O(n), reach for two pointers.
Implementation
function lowerBound(nums, target) {
let lo = 0;
let hi = nums.length; // half-open: hi is one past the last index
while (lo < hi) {
const mid = (lo + hi) >> 1; // floor((lo + hi) / 2), overflow-safe in JS
if (nums[mid] < target) lo = mid + 1; // mid is too small — discard it and everything left
else hi = mid; // mid might be the boundary — keep it, drop the right
}
return lo; // first index with nums[index] >= target (== length if none)
}Worked examples
Lower bound of a target — in the sorted array [1, 3, 5, 7, 9], find the first index whose value is at least 6. There is no 6, so the answer is the slot where 6 would go to keep the array sorted: index 3 (between 5 and 7).
Keep a half-open range [lo, hi). At each step look at mid: if nums[mid] < 6, then mid and everything left of it are too small — push lo past mid. Otherwise mid is a candidate boundary, so keep it and drop the right half with hi = mid. When lo === hi the range is empty and lo is the answer.
nums = [1, 3, 5, 7, 9], target = 6
Range is all five indices ([0, 5)). nums[2] = 5 is below 6, so index 2 and everything left is too small.
Now searching [3, 5). nums[3] = 7 is a candidate boundary, so keep it and discard the right half.
The range [3, 3) is empty. The loop ends with lo = 3.
Index 3 is the first position whose value (7) is >= 6 — exactly where 6 would be inserted.
function firstAtLeast(nums, target) {
let lo = 0;
let hi = nums.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] < target) lo = mid + 1; // boundary is strictly right of mid
else hi = mid; // boundary is at mid or to its left
}
return lo;
}The range shrinks from 5 to 2 to 0 in three steps — O(log n) time, O(1) space. The same skeleton, with the comparison swapped, gives the upper bound (first index > target), and the two together bracket a value's full run.
Things to look out for
- Mixing the two loop shapes:
lo <= hipairs withhi = mid - 1(exact search);lo < hipairs withhi = mid(boundary search). Crossing them either skips the answer or loops forever. - Computing
midas(lo + hi) / 2without flooring — use(lo + hi) >> 1orMath.floorsomidis an integer index. - On a boundary search, writing
hi = mid - 1discards the very index you were trying to land on —hi = midkeeps the candidate alive. - Re-checking a half you've already excluded (a linear fallback creeping in) silently degrades
O(log n)back toO(n).
Corner cases
- Empty input — return the not-found sentinel (
-1) or insertion index0before the loop body matters. - Single element — the loop must handle a range of size 1 without dividing by zero or skipping it.
- Target smaller than every element (answer
0) or larger than every element (answerlength). - Duplicates — decide whether you want the first or last matching index; an exact-match search lands on an arbitrary one.
- All elements equal to the target — the lower bound is
0and the upper bound islength.