- Define and explain Binary Search in your own words
- Use key terms such as binary search accurately
- Apply what you have learned to new examples and questions
- Avoid the common mistakes learners make with this topic
This lesson focuses on Binary Search: search sorted lists far faster by halving the problem.
Search sorted lists far faster by halving the problem.
Key ideas
Binary search needs sorted data
Binary search is dramatically faster than linear search — about 20 comparisons for a million items — but it only works if the list is sorted first. Sorting costs time too, so for a one-off search of unsorted data, linear search can still win. The right algorithm depends on the situation, not just the theory.
Halving the search
Each step compares the target with the middle item of the current range. If it matches, you are done; if the target is smaller, discard the upper half, and if larger, discard the lower half. Then repeat on the half that remains. Because the range halves every step, a million sorted items shrink to one in about 20 comparisons — that is O(log n) time, dramatically faster than checking each item in turn.
Key term — binary search: Repeatedly halving a sorted list to find a target — comparing with the middle item and discarding the half that cannot contain it.
Roughly how many comparisons does binary search need for 1,000,000 sorted items?
About 20 — each step halves the remaining items, so a million shrinks to one in roughly 20 halvings.
Answer: About 20 — each step halves the remaining items, so a million shrinks to one in roughly 20 halvings.
- Using binary search on an unsorted list Correction: sort the list first, or use linear search — binary search on unsorted data gives wrong answers, not just slow ones.
- Off-by-one errors when picking the middle Correction: with an even-length range there are two middle items — be consistent about which one you pick, or your trace will drift from the expected answer.
Practice
If the list is unsorted, binary search needs it sorted first — that sorting cost can outweigh the faster search for a one-off lookup.
False — it needs sorted data, and for tiny or unsorted lists the overhead is not worth it; the best algorithm depends on the situation.
5, then 9, then 7 — middle of [1,3,5,7,9,11] is 5; 7 is larger so search [7,9,11]; middle is 9; 7 is smaller so search [7]; found.
About 10 — 2¹⁰ = 1024, so ten halvings shrink 1,000 items to one.
Quick check
Which of these best defines "binary search"?
Why must the list be sorted before using binary search?
- Binary Search: search sorted lists far faster by halving the problem.
- Binary search needs sorted data: Binary search is dramatically faster than linear search — about 20 comparisons for a million items — but it only works if the list is sorted first.
- Halving the search: Compare with the middle, discard the half that cannot contain the target, and repeat — O(log n) time.
- Watch out for: using binary search on an unsorted list