Binary Search
Search a sorted array in O(log n) — halve the range with each comparison so one million items need only twenty.
What you'll learn
- Binary search requires a sorted array and halves the search range with every comparison
- The iterative implementation must use lo <= hi and update lo = mid+1 / hi = mid-1 to avoid infinite loops
- 1 million items need at most ~20 comparisons — O(log n) is the break-even point over linear
- Python's bisect module is the standard-library binary search for sorted inserts and range queries
Before you start
Imagine guessing a number between 1 and 100. Each time you guess, you’re told “higher” or “lower.” A smart player doesn’t start at 1 and count up — they guess 50. If the answer is higher, they guess 75. Each guess halves the remaining range. That’s binary search.
The phone-book analogy works the same way: to find “Smith,” you open near the end. If you land on “Taylor,” you know to go left. You never need to read every page. The key ingredient that makes this possible is that the data is sorted. Without that ordering, “go left” is meaningless.
Watch it run
Notice the comparison counter as you step through. Even with 15 elements the binary search finishes in at most 4 comparisons, while a linear scan could need all 15. The gap grows dramatically at scale.
The implementation
Python’s bisect module (bisect_left, bisect_right) is a production-
grade binary search. It returns the insertion point for a target value in
a sorted list — exactly the right tool for sorted-insert workloads and
range queries.
Why O(log n) matters
Each comparison eliminates half the remaining elements. Starting from n:
| Step | Remaining |
|---|---|
| 1 | n / 2 |
| 2 | n / 4 |
| k | n / 2^k |
The search ends when one element remains: n / 2^k = 1, so k = log2(n).
For 1 million items, that’s at most 20 comparisons. A linear scan could
need all 1,000,000.
The practical break-even is low. Even for a sorted list of 100 items, binary search takes at most 7 comparisons while linear takes up to 100. Once you’re searching the same sorted data more than a handful of times, binary search pays for itself immediately.
Binary search beyond simple lookup
The pattern extends further than textbook examples.
Sorted inserts with bisect. bisect.insort(my_list, value) keeps a
list sorted as you insert — it finds the right position in O(log n) and
inserts in O(n) for the shift. For read-heavy sorted collections that need
occasional insertions it is often the simplest correct choice.
Range queries. bisect_left(arr, lo) and bisect_right(arr, hi) give
you the slice boundaries for all values in [lo, hi] in O(log n) — no
scan needed.
Binary search on the answer. A common interview and competitive programming pattern: instead of searching an array, you binary search on the answer space itself. “What’s the minimum capacity that makes all packages fit in D days?” — if you can test a candidate capacity in O(n), binary searching the range of possible capacities gives O(n log n) total. The key requirement is that the feasibility check is monotonic — meaning once an answer becomes feasible it stays feasible as the value grows (or the reverse); there is no flip-flopping. The sorted array is just the simplest case of this principle.
Quick check
Quick check
Practice this in an interview
All questionsBinary search halves the search space each iteration to find a target in O(log n). The tricky part is not the idea but the boundary conditions: closed vs. half-open intervals, how to update lo/hi, and when to use lo < hi vs. lo <= hi. One clean template eliminates all the classic bugs.
Even after rotation, one of the two halves around mid is always fully sorted. Check which half is sorted, then decide whether the target falls inside it. If yes, narrow to that half; if no, search the other. This keeps binary search's O(log n) guarantee.
Binary search on the answer space (eating speed 1 through max pile size) rather than on the input array. For each candidate speed, greedily compute hours needed in O(n). The feasibility check is monotone — if speed k works, any speed above k also works — so binary search finds the minimum valid speed in O(n log m) time.
Because the array is sorted, you can place one pointer at the start and one at the end, then squeeze them inward. If the sum is too big, move the right pointer left; if too small, move the left pointer right. This converges in one pass with O(1) extra space.