Recap
- Binary search finds a target in a sorted list by starting at the middle and eliminating half of the remaining data at each check.
- Repeat until the target is found or no elements remain.
- Sortedness is required. On unsorted data it can give a wrong “not found”.
- Greatest number of checks for n items: halve n repeatedly until 1 is left, then add the final check. Equivalent: the smallest k with 2k − 1 ≥ n.
- Doubling the list adds one more check. Linear search would need twice as many.
- Binary search is often more efficient on sorted data; specific code is not examined.
Key relationships
| List size n | Greatest checks (binary) | Greatest checks (linear) |
|---|---|---|
| 7 | 3 | 7 |
| 15 | 4 | 15 |
| 100 | 7 | 100 |
| 1,000 | 10 | 1,000 |
| 1,000,000 | 20 | 1,000,000 |
| Situation | Search to use |
|---|---|
| Unsorted data | Linear search (binary search is not valid) |
| Large, sorted, searched often | Binary search |
| Target likely at the very front | Linear search may be quicker |
| Need to know the position | Either, after confirming the data is sorted for binary |
Assumptions
- The list is sorted in ascending order unless stated.
- “Check” means one comparison of the target with the middle element.
- When the number of live items is even, the middle can be either of the two central items; the greatest number of checks stays the same.
Method for counting the greatest number of checks
- Write the doubling sequence 1, 2, 4, 8, 16, 32, …
- Find the first power of two that is greater than n.
- The exponent of that power is the greatest number of checks.
- Sanity check: 2(checks − 1) is at most n.
Mistakes to avoid
- Using binary search on unsorted data.
- Reporting n ÷ 2 as the number of checks.
- Starting at the first element.
- Forgetting that the middle element is also eliminated after it has been compared.
- Thinking it is always faster than linear search.
Worked mini-example
A sorted list holds 100 values. Doubling: 1, 2, 4, 8, 16, 32, 64, 128. The first power of two greater than 100 is 128 = 27, so the greatest number of checks is 7. Check: 26 = 64 is at most 100 ✓.
Quick self-check
- What must be true of a list before binary search can be used?
- What is the greatest number of checks for 500 items?
- A search compares the target 20 with a middle value of 35 in a sorted list. Which part is eliminated?
Answers
- It must be in sorted order.
- 9, because 29 = 512 is the first power of two greater than 500.
- The middle value and everything above it (values of 35 or more).
Where marks are won and lost
Questions give a sorted list and a target and ask which value is checked first, which half is eliminated, or how many checks are needed. Another type asks for the greatest number of iterations for a list of a stated size: find the first power of two greater than n. A third type asks whether binary search can be used on a given list (check if it is sorted) or which search is better in a scenario. Always check sortedness before anything else.
Back to the full study guide for worked examples and explanations.