3.11 Binary searchHalve it, halve it again

Binary search starts at the middle of a sorted data set and eliminates half of the data, based on whether the target is bigger or smaller than the middle element. It repeats this process on the remaining half until it finds the target or has eliminated every element. The data must be sorted for this to work: the whole trick depends on knowing that everything to the left of the middle is smaller.
| check | low | high | middle | value | decision |
|---|---|---|---|---|---|
| 1 | 1 | 15 | 8 | 36 | 63 > 36: keep right |
| 2 | 9 | 15 | 12 | 57 | 63 > 57: keep right |
| 3 | 13 | 15 | 14 | 70 | 63 < 70: keep left |
| 4 | 13 | 13 | 13 | 63 | found |
?Wait, why must the list be sorted?
How much faster is it? Each check cuts the remaining items roughly in half. Starting from n items, the number of checks in the worst case is about the number of times you can halve n before reaching 1, which is about log₂ n. For a million items, that's about 20 checks, against up to a million for linear search. Binary search is often far more efficient than linear search on sorted data. (The course doesn't test a specific way of coding binary search, only how it works and when it applies.)
| Sorted items | Linear search, worst case | Binary search, worst case |
|---|---|---|
| 15 | 15 checks | 4 checks |
| 100 | 100 checks | 7 checks |
| 1,000 | 1,000 checks | 10 checks |
| 1,000,000 | 1,000,000 checks | 20 checks |
| 1,000,000,000 | 1,000,000,000 checks | 30 checks |
?Wait, how do I get the binary search number without logarithms?
I thought about it. Show me
- Check 1: low 1, high 15, middle 8, value 36. 5 < 36, so keep the left half: high becomes 7.
- Check 2: low 1, high 7, middle 4, value 18. 5 < 18: high becomes 3.
- Check 3: low 1, high 3, middle 2, value 9. 5 < 9: high becomes 1.
- Check 4: low 1, high 1, middle 1, value 4. 5 > 4: low becomes 2. Now low is greater than high, so nothing is left: 5 is not in the list.
Why?
Even a failed search takes only about log₂ n checks. Linear search would have checked all 15.
Answer: Middles checked: 36, 18, 9, 4. After 4 checks every element is eliminated, so the search reports that 5 is not found.
Stuck? Get a hint
- Start with the middle of all 15: index 8.
- Each time 5 is smaller, keep only the left part.
- When the part left is empty, the value isn't there.
- AIt works on any list, sorted or not.
- BIt always checks every element.
- CIt requires sorted data and eliminates about half the remaining elements with each check.
- DIt is slower than linear search for large sorted lists.
Show the answer
C. Binary search needs sorted data and halves the search space each step, which makes it much faster than linear search on large sorted lists.
- A16
- B30
- C245
- D60,000
Show the answer
A. 2¹⁵ = 32,768 is too small and 2¹⁶ = 65,536 covers 60,000, so at most 16 checks. 60,000 is the linear search worst case.

If a binary search question doesn't say the list is sorted, check that first. "The list is not sorted" makes every binary search answer wrong, and sorting it first might cost more than one linear search.
- Binary search: check the middle of sorted data, eliminate half, repeat.
- The data must be sorted. Linear search works on anything.
- Worst case: about log₂ n checks. Doubling n adds one check.
- On large sorted data, binary search is usually far more efficient than linear search.