Lesson 07 of 16 · 21:51
Binary search
Binary search is not mainly about finding a number in a sorted array. It is about eliminating half of an ordered search space because one test proves that an entire region cannot contain the answer. The ordering may come from sorted values or from a false-then-true predicate.
Most bugs come from mixing interval conventions. Decide what lo and hi mean, which candidates are still possible, and whether mid remains possible after the comparison. Keep the code consistent with that contract.
What you should be able to do after this lesson
- Write the search interval invariant
- Prove which half can be discarded
- Test boundaries and absent answers
The mental model
Maintain an interval that still contains the answer. The midpoint test proves one portion impossible, so discard it without inspecting every element.
Recognize it when: Look for sorted order, a monotonic predicate, ‘first/last valid,’ or an optimization question whose candidate answer can be checked as feasible or infeasible.
The invariant to say aloud: If an answer exists, it remains inside the active interval; every discarded index has been proved unable to satisfy the target contract.
Learn the ideas one at a time
Concept 1 of 5
Traditional search
Watch from 0:00 ↗Compare target with arr[mid]. Equality returns; too small discards mid and everything left; too large discards mid and everything right.
In a sorted array, comparing target with arr[mid] classifies mid and one whole side. If arr[mid] is too small, every index at or left of mid is also too small; if too large, every index at or right is too large. That proof is what permits the logarithmic elimination.
Walk through an example
Find 7 in [1, 3, 5, 7, 9]. Mid is 5, so discard 1, 3, 5. The next mid is 7 and succeeds. Five candidates became two after one comparison.
In an interview
Do not say “because it is sorted” alone; explain the inequality that makes the discarded half impossible.
Concept 2 of 5
Boundary contract
Watch from 0:00 ↗Choose closed [lo, hi] or half-open [lo, hi) bounds and make the loop, updates, and return value consistent. Most binary-search bugs are contract mismatches.
For a closed interval [lo, hi], both endpoints are candidates and the loop usually runs while lo <= hi. After classifying mid, use lo = mid + 1 or hi = mid - 1. A half-open interval [lo, hi) uses different conditions and updates. Either is correct; mixing them loses or repeats candidates.
Walk through an example
In [lo, hi] with one remaining item, lo == hi and that item must still be tested. A loop using lo < hi would skip it unless designed specifically for boundary convergence.
In an interview
Say “the answer, if present, remains inside ...” and keep that sentence true after every update.
Concept 3 of 5
Condition search
Watch from 7:27 ↗When predicate(x) changes only once, search for the first true or last false. Store the boundary candidate or use bounds that converge directly to it.
Many problems ask for the smallest feasible capacity, earliest valid time, or first bad version. Define a monotonic predicate whose answers look like false, false, ..., true, true. Binary search then locates the transition rather than a particular array element.
Walk through an example
If capacity 5 fails, every smaller capacity also fails; if 8 succeeds, every larger capacity succeeds. Testing 6 or 7 narrows the first-success boundary without evaluating every capacity.
In an interview
Spend more time proving predicate monotonicity than writing the loop. If truth can flip back, binary search is invalid.
Concept 4 of 5
Complexity
Watch from 10:06 ↗Each test halves the remaining candidates, so there are O(log n) tests. Total time is O(log n × cost(predicate)).
Each test reduces the candidate count by about half, so after k tests at most n / 2^k candidates remain. Setting that near one gives k = O(log n). If the predicate scans data in O(n), the total is O(n log range), not merely O(log range).
Walk through an example
A million ordered candidates require about 20 halvings because 2^20 is roughly one million. That is why binary search scales to enormous ranges.
In an interview
Multiply the number of iterations by the cost of one predicate evaluation and name whether the range is n or a numeric answer range.
Concept 5 of 5
Implementation
Watch from 13:28 ↗Use mid = lo + (hi - lo) // 2, move past mid after it is classified, and test empty, one-item, absent, and boundary answers.
Compute mid from the current bounds, classify it once, and move a bound past mid so the interval strictly shrinks. Decide whether you are returning an exact index, an insertion position, or a first-valid boundary; those are different contracts even when the loop looks similar.
Walk through an example
Test an empty range, a one-item hit, a one-item miss, a target below all values, above all values, and duplicates at the desired boundary. These cases exercise every endpoint decision.
In an interview
Use a known template only after describing its return contract. Memorized updates without an invariant are fragile under variant questions.
Before you call this lesson done
- Define the candidate interval
- Prove the discarded side impossible
- Move past a classified mid
- Test empty, absent, duplicate, and endpoint answers
