Searching: Linear and Binary Search
Searching is the most common thing programs do, and it comes in two speeds. Linear search checks every element: O(n), works on anything. Binary search halves the search space each step: O(log n), but demands sorted data. The gap between them is enormous: finding one item among a billion takes a billion checks linearly, but only about 30 with binary search. This lesson teaches you both, plus the off-by-one discipline binary search requires.
What You'll Learn
- Linear search and when it is the right choice
- Binary search: the algorithm, the implementation, and the classic pitfalls
- Python's built-in
bisectmodule - How to recognize "binary searchable" problems
Linear Search
Walk the sequence until you find the target. No preconditions, works on unsorted data, and for small lists it is unbeatable in simplicity:
Binary Search: Halve Until Found
If the data is sorted, compare the target with the middle element. Too small? The answer lives in the right half. Too big? Left half. Each comparison throws away half the remaining candidates:
One million elements, about 20 steps. Memorize the invariants:
loandhibracket the region that might still contain the target- Loop while
lo <= hi - Move
lo = mid + 1orhi = mid - 1(skippingmid, which you just checked)
Most binary search bugs come from breaking one of these: using lo < hi with the wrong updates, or setting hi = mid and looping forever.
bisect: Binary Search, Batteries Included
Python ships binary search in the bisect module. bisect_left returns the index where a value would be inserted to keep the list sorted, which doubles as "index of the first element >= target":
Thinking in Binary Search
Binary search is bigger than "find x in a sorted list." It works on any monotonic yes/no question: if the answers look like no, no, no, yes, yes, yes, binary search finds the boundary in O(log n). Guessing games, "first version that fails" problems, and capacity planning all fit. Try the guessing game fullscreen:
Seven guesses always suffice for 1 to 100, because 2^7 = 128 > 100.
Choosing a Search
- Unsorted data, one search: linear, O(n). Sorting first costs O(n log n), so it only pays off across many searches
- Sorted data: binary search, O(log n)
- Many membership tests, order irrelevant: build a set once, O(1) per lookup
- Sorted data you also insert into:
bisect.insortkeeps it sorted in O(n) per insert
Exercises
Key Takeaways
- Linear search is O(n), needs no preparation, and is fine for small or unsorted data
- Binary search is O(log n) but requires sorted data and careful bounds:
lo <= hi, move past mid on each side bisect_leftgives you production-ready binary search and insertion points- Binary search generalizes to any monotonic condition, not just sorted lists
- One million items: 20 comparisons. That is the power of halving