What you'll learn
Searching is the most basic task in computing — and binary search is the first place you feel the power of a good algorithm: it finds an item among a billion in about 30 steps. You'll also learn to generalize it into binary search on the answer, one of the sharpest tools in the box.
By the end you'll be able to:
- Compare linear and binary search
- State and rely on binary search's invariant
- Write binary search without the classic off-by-one and overflow bugs
- Recognize when to binary-search the answer
Linear search
The obvious approach: check each element until you find the target. It works on any list, sorted or not, but it costs O(n) — potentially every element:
Binary search
If the array is sorted, you can do far better. Look at the middle: if it's the target, done. If the target is larger, it must be in the right half; if smaller, the left half. Each comparison halves what's left — O(log n). The invariant: if the target is present, it's always within [lo, hi].
Key idea
O(n log n)) then binary-searching (O(log n) each) beats repeated linear scans.In code
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # avoids overflow
if a[mid] == target:
return mid # found
elif a[mid] < target:
lo = mid + 1 # go right
else:
hi = mid - 1 # go left
return -1 # not foundWatch out
mid = (lo + hi) / 2 can overflow for large indices (use lo + (hi - lo) / 2), and mixing up <= vs < in the loop condition causes off-by-one errors. Pin down your invariant and the boundaries follow.Binary search on the answer
The real superpower: binary search doesn't need an array at all. If you can ask a yes/no question that flips from "no" to "yes" at some threshold — a monotonicpredicate — you can binary-search for that threshold. "Is a machine speed of x fast enough to finish in time?" is false for small x and true for large x; binary-search the smallest x that works.
Tip
O(n) answer-space into O(log n) checks.Complexity
| Search | Requires | Time | Space |
|---|---|---|---|
Linear | Nothing | O(n) | O(1) |
Binary | Sorted data | O(log n) | O(1) iterative |
Binary on answer | Monotonic check | O(log(range) × check) | O(1) |
Recap & quick check
Key takeaways
- Linear search is O(n) and works on any data; binary search is O(log n) but needs sorted data.
- Binary search halves the range each step; invariant: the target stays within [lo, hi].
- Use mid = lo + (hi - lo)/2 to avoid overflow, and be careful with <= vs <.
- Binary search on the answer solves any monotonic yes/no threshold problem.
- Sorting once then binary-searching beats repeated linear scans.
Quick check
1. What is the time complexity of binary search?
2. What must be true for binary search to work?
3. Why prefer mid = lo + (hi - lo) / 2?
4. 'Binary search on the answer' applies when the check is:
Binary search assumed sorted data. Time to learn how to produce it. Next up: Module 7 — Elementary Sorts.