Think together · Start with a little story
The robot halves a set of 16 possible positions. The girl sees that after just a few steps, very few candidates remain.
Lay out the process
- 16 candidatesReduce to about 8
- 8 candidatesReduce to about 4
- 4 candidatesReduce to about 2
- 2 candidatesReduce to about 1
Halving the candidate set each time means the number of steps grows slowly, logarithmically.
If the data size doubles, binary search usually needs only one more halving step. This diagram shows how the candidate set changes, not the exact comparisons of a particular implementation.
How can each step rule out half?
Find 7 among cards sorted from smallest to largest. Gray cards have been ruled out.
The middle value, 5, is less than 7. It and everything to its left cannot be the target.
Using the lower middle index, compare the value at index 3, which is 7.
Return index 3, the fourth card. There is no need to check 9.
01What does binary search do each time?
It does more than check one element. More importantly, each comparison lets it rule out about half of the candidates.
02How many halvings does it take for 1,024 elements?
Because:
It takes about 10 halvings.
03What does log₂n tell us?
You can think of log₂ n as asking:
Equivalently: about how many times must you keep dividing n by 2 to get down to 1?
04Why write O(log n) instead of O(log₂ n)?
Logarithms with different bases differ only by a constant factor:
Asymptotic Big O analysis ignores fixed constant factors, so we usually write O(log n).
05How slowly does O(log n) grow?
| n | Approximate log₂ n |
|---|---|
| 1,024 | 10 |
| 1,048,576 | 20 |
| About 1 billion | 30 |
The input can grow many times larger while the number of operations increases only a little.
06Does halving every time always mean O(log n)?
If each round does O(1) extra work and the problem size shrinks by a fixed ratio each round, the common result is indeed O(log n).
If each round also does a lot of work internally, include that computation when analyzing the total complexity.
What have you learned?
- Binary search roughly halves its candidate range in every round.
- Repeatedly halving n down to 1 takes about log₂ n rounds.
- Therefore, binary search takes O(log n) time.
- Big O notation usually leaves out the logarithm’s base.
- O(log n) grows very slowly.
Next: How Can You Make a Slow Program Faster?
Your turn to try
If 16 candidates become 32, does the number of halvings roughly double?
Ready? Open to see the explanation
No. It usually adds only one round: first reduce 32 to about 16, then follow the original process.