← Binary Search · guided lesson
Binary Search
the story
Binary search
Every tool here exists because something was too slow or broke without it. Here is what.
Binary search was first mentioned by John Mauchly in the 1946 Moore School Lectures, the first course on building electronic computers — as Knuth records in The Art of Computer Programming, Vol. 3. Early published versions only worked when the table had 2ᵏ − 1 entries; D. H. Lehmer published one that works for any n in 1960. It stayed tricky: in Jon Bentley's courses at Bell Labs and IBM, about 90% of professional programmers found bugs in their own binary search (Programming Pearls).
the problem it solved
Finding an item among n sorted ones with about log₂ n comparisons instead of up to n.
why it matters: without it
Every lookup in sorted data would be a full scan; finding a bad commit among 1,000 would take up to 1,000 test runs instead of about 10.
sources: Knuth — The Art of Computer Programming, Vol. 3: Sorting and Searching, §6.2.1 ↗ · Lehmer — Teaching combinatorial tricks to a computer (Proc. Symp. Applied Math. 10, AMS, 1960) ↗ · Bentley — Programming pearls: Writing correct programs (CACM, 1983) ↗
also in this chapter: Lower bound & upper bound (boundary search) · The overflow-safe midpoint · Binary search on the answer
the idea
The idea in 30 seconds
Look at the middle of what's left. One comparison tells you which half cannot hold the answer — throw that half away.
Halving n until 1 is left takes about log₂ n steps: 1,000,000 items → 20 looks, 1,000,000,000 → 30.
It works on anything monotonic: a sorted array, or any yes/no question that flips from no to yes exactly once.
picture this
Finding "Priya" in a sorted contact list of 1,000 names without scrolling: jump to the middle (say "Meera"). Priya comes later, so the whole first half is gone. Jump to the middle of what's left, and again — about 10 jumps, never 1,000.
watch it
Classic binary search — watch the space halve
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Classic binary search — watch the space halve
Grey cells are ruled out for good. Count the looks: never more than ⌊log₂ n⌋ + 1.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Lower bound with lo < hi
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Lower bound with lo < hi
With duplicates, keep shrinking towards the *first* match. `hi = mid` keeps mid alive because it might be the answer.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
Binary search needs a monotonic property: sorted values, or a yes/no test that goes no no no yes yes yes. Not sorted? Then you need some other reason to discard a half (rotated arrays, peaks).
key idea 2 of 8
Read it once. Say it out loud once. Bas.
Keep a search space and an invariant — a sentence that is always true about it, like "if the target exists, it is inside [lo, hi]". Every update must keep the sentence true.
key idea 3 of 8
Read it once. Say it out loud once. Bas.
Template 1 — find exactly: lo = 0, hi = n−1, while (lo <= hi), move with lo = mid + 1 / hi = mid − 1. Stops when the space is empty.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
Template 2 — find a boundary: lo = 0, hi = n, while (lo < hi), move with hi = mid / lo = mid + 1. Stops when one candidate is left; that candidate is the answer.
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Compute mid = lo + (hi − lo) / 2. The tempting (lo + hi) / 2 overflows when lo + hi > 2³¹ − 1 — a real bug that sat in the JDK for years.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
Lower bound = first index with a[i] >= x; upper bound = first index with a[i] > x. Count of x = upper − lower. First/last occurrence and insert position all fall out of these two.
key idea 7 of 8
Read it once. Say it out loud once. Bas.
Arrays.binarySearch / Collections.binarySearch return the index if found, otherwise -(insertionPoint) − 1 — always negative. With duplicates, which match you get is not specified.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Binary search on the answer: when the question is "smallest speed / capacity / time that works" and bigger always works if smaller does, binary search the answer range and test each guess with a fast greedy check.
spot the pattern
When you see this, think this
Input is sorted (or each row of a matrix is) and you need O(log n)
Classic binary search or lower/upper bound
"First", "last", "insert position", "how many equal to x"
Lower bound / upper bound (lo < hi template)
"Minimum capacity / speed / time / largest minimum such that …"
Binary search on the answer with a greedy feasibility check
Sorted array that was rotated
Compare mid with an end to find which half is sorted
+5 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Infinite loop: using
lo = midwithmid = lo + (hi − lo) / 2in alo < hiloop. Whenhi = lo + 1, mid == lo and nothing moves. Either uselo = mid + 1, or round mid up (lo + (hi − lo + 1) / 2). - Mixing templates:
while (lo < hi)withhi = mid − 1, orwhile (lo <= hi)withhi = mid. Pick one template and keep all three parts consistent.
quick check
One question. No pressure.
About how many looks does binary search need, at most, for 1,000,000 sorted items?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Binary Search
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Why does binary search need only about log₂ n looks?
Question 1: Why does binary search need only about log₂ n looks?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.