🧮Binary Search
Also known as Half-Interval Search, Bisection Search
Finding an item in a sorted list. Each step cuts the search in half.
Think of it like
Think of it like a phone book. Open it in the middle, then pick a half.
Example
Lucy searches 1,000,000 sorted names for one name. Binary search finds it in at most 20 checks.
Why it matters
It turns a search of millions into a handful of steps. Databases and many libraries use it inside.
Definition
Example code
python
>>> import bisect
>>> bisect.bisect_left([2, 5, 8, 12, 20], 12)
3Common mistake
Key takeaways
- 1Sorted lists only. Or the answer is wrong.
- 2Halve each step. Check the middle.
- 3O(log n). 20 checks for a million.