Guess the number
I am thinking of a number between 1 and 100. After each guess I say "higher" or "lower". What do you guess first?
Almost everyone says 50. Not because 50 is likely to be right, but because whichever answer comes back, half of the possibilities are gone. Then 25 or 75, and half are gone again.
That is binary search. It works on anything sorted, and it is astonishingly fast.
How it works
Keep track of the range that could still hold the target
Two markers,
loandhi. At first they cover everything.Look at the middle item
One comparison.
If it is the target, stop
Found.
If it is too small, throw away the left half. If too big, the right half
Because the items are sorted, the target cannot be on that side.
Repeat until found, or until the range is empty
An empty range means the target is not there.
Pick a target and step through it. Greyed-out items have been ruled out.
1lo, hi = 0, len(items) - 12while lo <= hi:3 mid = (lo + hi) // 24 if items[mid] == target:5 return mid6 if items[mid] < target:7 lo = mid + 18 else:9 hi = mid - 110return -1
Variables
nothing yet
Start. Press play, or step through one line at a time.
Why it is so fast
Each check halves what is left. Going the other way: each extra check lets you search twice as many items.
| Items | Checks needed, at most |
|---|---|
| 10 | 4 |
| 1,000 | 10 |
| 1,000,000 | 20 |
| 1,000,000,000 | 30 |
A thousand times more data costs ten more checks. Checking items one by one would need a million checks for a million items. This growth is written O(log n).
The bug in the textbook version
For decades, the standard way to compute the middle was:
int mid = (lo + hi) / 2;It looks harmless, and it was in widely used libraries for years before anyone noticed the problem. With a large enough array, lo + hi is bigger than the largest number an int can hold. It overflows and wraps around to a negative number.
1int lo = 1_500_000_000;2int hi = 2_000_000_000;3int mid = (lo + hi) / 2; // the bug4int safe = lo + (hi - lo) / 2; // the fix
Variables
nothing yet
Start. An int holds values up to 2,147,483,647. Watch what happens to lo + hi in a very large array.
The fix computes the same value without ever forming the large sum:
int mid = lo + (hi - lo) / 2;hi - lo is the size of the range, which always fits. Languages whose integers grow as needed, such as Python, do not have this problem.
Off-by-one, the other classic
Most broken binary searches are wrong by one somewhere. The version in the animation follows three rules that go together:
histarts at the last valid position,len(items) - 1.- The loop runs while
lo <= hi, so a range of one item is still checked. - The middle is always excluded when narrowing:
lo = mid + 1orhi = mid - 1. Otherwise the range can stop shrinking and the loop never ends.
def binary_search(items, target):
lo, hi = 0, len(items) - 1
while lo <= hi:
mid = (lo + hi) // 2
if items[mid] == target:
return mid
if items[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1More than finding a value
The same halving idea answers any question of the form "where does the answer switch from no to yes?".
- Where should this value be inserted to keep the list sorted?
- Which commit introduced the bug? (
git bisectdoes exactly this.) - What is the smallest server size that passes the load test?
Key takeaways
- Binary search checks the middle of a sorted range and throws away the half that cannot contain the target.
- Each check halves the range: a million items in 20 checks, a billion in 30.
- It only works on sorted data.
- Compute the middle as lo + (hi - lo) / 2 to avoid overflow in languages with fixed-size integers.
- Always exclude the middle when narrowing, or the loop may never end.