Binary search, and why it is easy to get wrong
Looking something up in a sorted list is the one place where knowing an algorithm pays off immediately. Check the middle. If it is too small, everything to its left is too small as well, so all of it can go. If it is too big, the right half goes instead. Repeat on what is left.
The part worth watching is what that discards. Below, 16 sorted numbers, and a search for 23 settles it in 2 comparisons while looking at 2 of the 16 cells. The others are not skipped over quickly. They are never read at all.
Drag the target. Odd numbers are in the array and even ones are not, so you can watch a successful search and a failed one back to back. Then switch to linear to see what ignoring the sorting costs, and to buggy for the version almost everyone writes at least once.
1function search(a, target) {2 let lo = 0, hi = a.length - 13 while (lo <= hi) {4 const mid = (lo + hi) >> 15 if (a[mid] === target) return mid6 if (a[mid] < target) lo = mid + 17 else hi = mid - 18 }9 return -110}
The array
sorted, with the part still worth looking at
Looking for 23
- 1
- 3
- 5
- 7
- 9
- 11
- 13
- 15
- 17
- 19
- 21
- 23
- 25
- 27
- 29
- 31
16 of 16 still in play · 0 comparisons
Sixteen sorted numbers, and we are looking for 23. Everything is still in play, so the window covers all sixteen.
How the window halves, why sorting is load-bearing, and what the bug actually does.
Throwing away half, not looking twice as fast
The rule under the cells is the window: the part of the array that could still hold the answer. It starts covering everything and never grows. Every comparison either lands on the target or rules out one side of the cell you just checked, which is half of what was left.
That is why the discarded cells stay on screen rather than vanishing. The array is not getting smaller. Your obligation to look at it is.
Why it has to be sorted
Everything rests on one inference: if the middle value is too small, every value to its left is too small as well. That is only true because the array is in order. Hand the same algorithm an unsorted array and it will confidently discard the half containing the answer, then report that the answer is not there. It will not crash, and it will not look wrong.
Absence costs what presence costs
Search for 24. It is not in the array, and finding that out takes the same handful of comparisons that finding 23 did. The window halves until it is empty, and an empty window is proof: not a failure to look hard enough, but a demonstration that there was nowhere left the value could have been hiding.
Now switch to linear and search for 31, the last value. That takes 16 comparisons, because linear search has no way to rule anything out and has to walk the whole row. It is reading the same numbers; it just learns almost nothing from each one.
The bug
Switch to buggy and search for an even number below 31. The only difference is on line 7: the high end of the window moves to mid rather than mid - 1, so the cell that was just ruled out stays in the window.
Watch what that does. The window shrinks normally until it holds one cell, and then stops. The loop keeps checking the same cell, gets the same answer, and narrows to the same window. Nothing crashes. No wrong value is returned. The search simply never ends, and on screen it looks almost exactly like a search that is still working.
The overflow nobody notices
The obvious way to find the middle is (lo + hi) / 2. In a language with fixed-width integers, that addition can overflow before the division happens, which turns the midpoint into a negative number and the lookup into an out-of-bounds read.
This is not a theoretical concern. It sat in the JDK's Arrays.binarySearch for nine years, and in Jon Bentley's published version for two decades before that, on the reasoning that arrays big enough to trigger it did not exist yet. Then they did. The fix is lo + (hi - lo) / 2, which never adds two large numbers together.
The animation uses (lo + hi) >> 1, which is the same arithmetic with the same weakness, and is safe here only because the array has 16 cells.
Why the loop is the hard part
There are four decisions in a binary search and each has two plausible answers: whether the loop runs while lo <= hi or lo < hi, whether hi starts at length - 1 or length, and whether each end moves past the midpoint or onto it. Most combinations are wrong, and they fail in different ways: some miss the last element, some loop forever, some read out of bounds.
The way to keep them straight is to name what the window means and never break it. Here it means every index from lo to hi inclusive might still hold the target. Once that is fixed, the rest follows: hi starts at the last valid index because that index might hold the target; the loop continues while lo <= hibecause a window of one is still a window; and both ends move past the midpoint because the midpoint has just been ruled out.
When it is worth it
Sorting to enable one binary search is a bad trade: the sort costs more than the linear scan you were avoiding. It pays when the array is searched many times, or arrives sorted anyway, which is the common case in databases and on disk.
The shape also outlives the array. Anything with a monotonic answer can be searched this way, whether or not there is a list involved: the smallest capacity that finishes a job in time, the first version where a test starts failing, the point where a function crosses zero. Git ships this as git bisect, and it is the same five comparisons over a thousand commits.
Three questions
Pick an answer before you open one. Being wrong here is the useful part, and it is the whole reason to answer rather than read.
The array holds 16 sorted numbers. At most how many comparisons does a correct binary search need to find one, or prove it is absent?
Searching for 24, which is not in the array at all, compared with searching for 23, which is. Which costs more?
A binary search moves the high end to mid instead of mid minus one. Every test that searches for a value that exists passes. What happens on a value that does not?
Problems
Work them before opening the answers. Reading a solution feels like learning and is not.
Count the comparisons
An array of 1,000 sorted values.
About how many comparisons does binary search need
in the worst case? And 1,000,000?Show the answer →Hide the answer
About 10 for a thousand, about 20 for a million.Doubling the array adds one comparison. Going from a thousand to a million multiplies the work by two, not by a thousand, which is the entire reason anyone bothers.
The missing half
function search(a, target) {
let lo = 0, hi = a.length - 1
while (lo < hi) {
const mid = (lo + hi) >> 1
if (a[mid] === target) return mid
if (a[mid] < target) lo = mid + 1
else hi = mid - 1
}
return -1
}Show the answer →Hide the answer
while (lo <= hi)With lo < hi the loop exits while one cell is still unchecked, so any target sitting in that last cell is reported missing. It passes most tests, because most tests do not search for the value that happens to end up alone.
First, not any
The array contains duplicates:
[1, 3, 3, 3, 7, 9]
Plain binary search finds *a* 3. Change it to
return the index of the *first* 3.Show the answer →Hide the answer
function firstOf(a, target) {
let lo = 0, hi = a.length - 1, best = -1
while (lo <= hi) {
const mid = (lo + hi) >> 1
if (a[mid] === target) {
best = mid
hi = mid - 1 // keep looking left
} else if (a[mid] < target) lo = mid + 1
else hi = mid - 1
}
return best
}Finding a match is not the end of the search. Record it and carry on into the left half, because an earlier one may still be there. This is the shape behind lower_bound in most standard libraries.
Search without an array
A function isBadVersion(v) returns false for every
version up to some point, and true from then on.
Find the first bad version, with as few calls as
possible.Show the answer →Hide the answer
function firstBad(n) {
let lo = 1, hi = n
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1)
if (isBadVersion(mid)) hi = mid
else lo = mid + 1
}
return lo
}There is no array here, only a question with a yes/no answer that flips once and never flips back. That monotonic flip is all binary search ever needed. Note that hi = mid is correct in this version, because mid has not been ruled out.
Rotated
A sorted array has been rotated at an unknown point:
[7, 9, 11, 1, 3, 5]
Find a target in it, still in logarithmic time.Show the answer →Hide the answer
function search(a, target) {
let lo = 0, hi = a.length - 1
while (lo <= hi) {
const mid = (lo + hi) >> 1
if (a[mid] === target) return mid
if (a[lo] <= a[mid]) {
if (a[lo] <= target && target < a[mid]) hi = mid - 1
else lo = mid + 1
} else {
if (a[mid] < target && target <= a[hi]) lo = mid + 1
else hi = mid - 1
}
}
return -1
}At least one side of the midpoint is always still in order, and you can tell which by comparing the midpoint with an end. Check whether the target falls inside that sorted side; if it does, search there, and if not, search the other. The rule that made the first version work has not changed, only the way you work out which half to keep.
What gets asked, and what a good answer sounds like
Say these out loud rather than reading them. The gap between knowing something and being able to say it is the thing interviews measure.
+Why is binary search logarithmic?
Each comparison rules out half of what is left, so the question is how many times you can halve the array before one cell remains. That is log base two of its length. Doubling the input adds one comparison rather than doubling the work.
+What does it require of the input?
Sorted order, and the ability to jump straight to any position. Sorted, because the whole method rests on inferring that everything left of a too-small value is also too small. Jumping, because reaching the midpoint has to be cheap; on a linked list you would pay linear time to get there and lose the advantage entirely.
+Write it on the board. What will you get wrong?
The boundaries. State the invariant first and let it settle the rest: every index from lo to hi inclusive might still hold the target. That gives you hi starting at length minus one, a loop condition of lo less than or equal to hi, and both ends moving past the midpoint rather than onto it.
The classic failure is moving hi to mid instead of mid minus one. It still finds anything that is present, so tests pass, and then it never terminates on a value that is absent.
+Is (lo + hi) / 2 safe?
Not in a language with fixed-width integers. The addition can overflow before the division, giving a negative midpoint and an out-of-bounds read. Use lo plus (hi minus lo) over two. This was a real bug in the JDK for nine years, so it is a fair thing to be asked about.
+Where would you use it outside a sorted array?
Anywhere the answer is monotonic: a predicate that is false up to some point and true after it. Finding the first failing version, the smallest capacity that meets a deadline, the point where a function crosses zero. Git bisect is the everyday example, and it is the same handful of comparisons over thousands of commits.
Know someone stuck on this? Send it to them.
A classmate, a study group, someone learning this on their own at midnight. The link opens the lesson set up exactly as you have it, the same function and the same number, and runs from the first step so they watch the whole thing build rather than landing in the middle of it.
Also in this course
Recursion: how a function calls itself
The call tree and the call stack side by side, so you can watch a call pause, wait, and pick up exactly where it left off.
Start there →