What is binary search?
Binary search repeatedly cuts a sorted search space in half. It compares the middle element to what you're looking for, throws away the half that can't contain the answer, and repeats on what's left — turning a scan of every element into O(log n) comparisons.
- Search space
- The range of indices —
lowthroughhigh— that might still hold the answer - Midpoint
- The index halfway between
lowandhigh, compared against the target each step - Boundary
- The point where a condition flips from false to true — often what you're really searching for
Why binary search at all?
Picture looking up a word in a paper dictionary. You don't start at page one and read every entry — you open to the middle, see which half the word falls in, and open to the middle of that half. A few flips and you've narrowed a thousand pages down to one.
Each flip throws away half of what's left. A dictionary of a million words takes about twenty flips to search — compare that to reading straight through.
Every flip halves what's left. Three flips settle a list of seven.
What kinds of problems does it solve?
Four common shapes. The halving never changes — you only change what the comparison at the midpoint asks.
Find an exact value
On a sorted array, compare the target to the middle element. Equal is a match. Smaller means
the target can only be to the left, so high moves in. Larger means low moves
in.
9 > 7 → the answer can only be to the right of mid.
Find the first index where a condition flips
The array isn't values to match — it's a condition that's false, then true, from some point on. When the middle is true, that's a candidate answer, but there might be an earlier one — keep searching left.
A true at mid is a candidate — but keep checking left for an earlier one.
Find where a value should be inserted
Same halving, but the target may not be in the array at all. When low passes
high, low itself is the index where the value belongs to keep the array
sorted.
6 never matches a cell — low ends up sitting exactly where it belongs.
Search over a range of possible answers
The array can be imaginary. Binary search over candidate answers instead of array indices — guess a value, check whether it's "good enough," and halve the range of guesses each time.
The "array" is just the numbers 1 through 6 — halved the same way.
Two types
Underneath, it's really only two shapes: search for an exact value and stop the moment you find it, or search for a boundary and keep going even after you find a candidate, because an earlier one might exist.
Exact-match search
low starts at 0, high starts at the last index. Every step compares
arr[mid] to the target and moves exactly one bound — never both. The loop ends the
moment it finds a match, or when low passes high.
Stop the instant mid matches — there's nothing left to check.
function exactMatch(arr: number[], target: number): number {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
const mid = low + Math.floor((high - low) / 2);
if (arr[mid] === target) return mid; // found it, stop now
if (arr[mid] < target) low = mid + 1; // answer is to the right
else high = mid - 1; // answer is to the left
}
return -1; // low crossed high, target isn't present
}
Boundary / predicate search
The comparison becomes a yes/no question instead of an equality check. A true at
mid is only a candidate — record it and keep searching left in case an earlier index
is also true. low ends up sitting on the boundary itself.
A true at mid never ends the search early — low is the real answer.
function firstTrue(n: number, isBad: (i: number) => boolean): number {
let low = 0;
let high = n - 1;
while (low < high) {
const mid = low + Math.floor((high - low) / 2);
if (isBad(mid)) high = mid; // mid could be the boundary, keep it in range
else low = mid + 1; // mid is false, boundary is strictly after it
}
return low; // low === high, sitting exactly on the boundary
}
Where it works — and where it breaks
Binary search leans on a quiet assumption: comparing the target to arr[mid] tells you,
with certainty, which half to discard. That's only true when the array is sorted — or, for
boundary search, when the condition is monotonic (all false, then all true, with no flipping
back).
Works on a sorted array
Target smaller than mid only ever means it's also smaller than everything to mid's right —
moving high in is provably correct. The order guarantees the discarded half never
held the answer.
Breaks on an unsorted array
The same "smaller than mid, go left" rule now has no guarantee behind it. It can throw away the half that actually held the target and never look back — with no error, just a wrong answer.