Algorithms & Complexity
It is like…
Binary search is a phone book trick
Binary search is like finding a name in a phone book
Quick check · tap an answer to continue
Lesson notes
Key points
- You open a phone book in the middle, see you passed your name, and toss away half the pages.
- The sorted pages are the sorted array, the middle page is the midpoint, and tossing half is halving the search range.
- It breaks because you jump straight to any index in constant time, and if the data is unsorted, halving tells you nothing at all.
Takeaway: Binary search halves a sorted range each step: O(log n).
Quick check: What must be true of an array before binary search works on it?
- It must be sorted
- It must have even length
- It must hold no duplicates
Discarding half only works if order tells you which half the target is in.
Phone bookThe mappingWhere it breaks
Lessons like this, for your syllabus.
Short narrated study videos written for your course, level and exam. Free to start.
Get lessons for your own syllabus