Binary Search
How to find something in a sorted list without looking at most of it. (“Binary” just means two — every check splits what is left into two halves and throws one away.)
The job
You have a list of numbers that is already sorted, smallest to largest. You need to know whether one particular number is in it — and if so, where.
The obvious way
Start at the first number and check them one at a time until you hit it. That works, and for a short list nobody would care.A list of 1,000,000 can cost 1,000,000 checks.
The idea
Because the list is sorted, checking the value in the middle tells you which side your number must be on. So you can throw the entire other side away without ever looking at it — then do the same thing again on what is left.
Think of it like this. Looking up a word in a paper dictionary. You do not start at page 1 and read forwards — you open it near the middle, see whether your word comes before or after, and ignore half the book. Then you do it again. Six or seven flips gets you to any word out of a hundred thousand. The catch is the same one binary search has: it only works because a dictionary is in alphabetical order.
Searching for 23
12 numbers, already sorted smallest to largest. We want to find 23.
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1This run
Found 23 at index 4 after 4 looks — checking one at a time would have taken 5.
The three names you just watched
lo and hi
The two ends of the part you have not ruled out yet. Everything outside them has already been proven impossible, so it is never looked at again.
mid
The one value you actually check each round — the middle of what is left. Checking the middle is what guarantees you drop half, rather than one item. In the code, // is Python for divide-and-round-down, not a comment.
Why sorted matters
Sorted order is what lets one value speak for everything behind it. On an unsorted list a single check tells you nothing about any other item, and the whole trick collapses.
How to spot a binary search problem
The tell: The data is sorted (or can be), and you are looking for one thing — or for the boundary where an answer flips from “no” to “yes”. If checking one item tells you something about everything on one side of it, you can halve.
Reach for it when
- The input is described as sorted, or sorting it first is allowed.
- You are asked to find a value, or the first/last position satisfying something.
- The problem size is huge (10⁵, 10⁹) but the time limit implies far fewer checks.
- You can ask a yes/no question whose answer, once it flips, stays flipped.
Not this when
- The data is unsorted and cannot be sorted (order carries meaning).
- You need every match, not one — that is a scan, not a search.
- Checking an item tells you nothing about its neighbours.
- The list is tiny. A plain loop is simpler and just as fast.
Why halving wins so hard
Checking one at a time
1,024
checks, worst case · O(n)
Halving every time
11
checks, worst case · O(log n)
Doubling the list costs binary search exactly one more check. Going from a thousand values to a million — a thousand times more data — takes it from 11 checks to 21. And it needs no extra memory to do it: just the two numbers lo and hi, however big the list gets.
Where it goes wrong
Running it on data that is not sorted
Binary search does not crash on unsorted input — it quietly returns -1 for values that are sitting right there. Throwing away a side is only safe if everything on that side really is smaller (or bigger). The moment that is untrue, it discards the half holding the answer and never finds out.
This is the most common real-world cause: data you assumed was sorted, and was not.
Also wrong
while lo < hi — this quits while one item is still unchecked, so a value in the last remaining slot is missed. A window holding one item is still a window, so the test is <=.
Also wrong
lo = mid instead of mid + 1 — once two items are left, the window stops getting smaller and the loop runs forever. `mid` was just checked, so it must be excluded.
Practice
3 easy · 3 hardThe lesson, exactly. Write it once without looking, then check your loop condition and your mid update against the two traps above.
When the loop ends without a hit, lo is sitting exactly where the value would have to go. That is not a coincidence — it is the invariant.
There is no array — you are binary searching a boundary in a false/true sequence. Same halving, different haystack.
One half of a rotated array is always properly sorted. Work out which one, and you can still discard half per step.
Binary search the PARTITION point of the smaller array, not the values. The answer is a cut position where both halves balance.
Binary search the ANSWER, not an index: guess a maximum subarray sum, greedily check whether k splits suffice, and halve the guess range.