Binary search turns a hopeless-looking search into a handful of steps. It's a classic divide and conquer technique that finds a target inside a sorted sequence by cutting the search space in half on every comparison. If linear search is checking every face in a crowd, binary search asks the crowd to line up by height and steps straight to the right spot. 🎯

You'll see it everywhere — coding interviews, the Python standard library, database indexes, even git.

How It Works

Think of a 1990s phone book. You want Salinger. You don't start at Aaronson and read forwards. You flop the book open near the middle, see M, and instantly know two things: Salinger is to the right, and the entire left half can be thrown away forever. Split the right half. T — too far, drop it. Split again. Q. Then S. You converge on the page in roughly seven jumps instead of a thousand.

That's the whole intuition. Every step keeps three values:

a left pointer at the start of the live range

a right pointer at the end

a mid computed safely as left + (right - left) // 2

Compare arr[mid] to the target. Three outcomes: equal (done), too small (move left = mid + 1), too big (move right = mid - 1). Each comparison eliminates half the remaining candidates. After k comparisons, n items shrink to n / 2^k — that's why the cost is log_2 n. A sorted array of one million items finishes in about 20 steps. A billion, about 30. That's logarithmic search in action.

The non-negotiable rule: the data must already be sorted. Run it on an unsorted array and it will cheerfully return wrong answers without complaining.

Iterative vs Recursive

The two implementations solve the same problem with different shapes.

The iterative version uses while left <= right: and updates pointers in place. It's what most Python developers reach for: constant extra memory, no stack risk. Python's own bisect module is implemented iteratively in C.

The recursive version expresses divide-and-conquer more literally — each call solves a smaller subproblem of the same shape. It reads beautifully, but Python's default recursion limit is 1000, every call adds a stack frame, and there's no tail-call optimisation. For binary search this is rarely fatal, but it's pure overhead.

In interviews, write the iterative version unless asked otherwise. In real code, import bisect.

Complexity Analysis

Variant	Best time	Avg / worst time	Space
Iterative	O(1)	O(log n)	O(1)
Recursive	O(1)	O(log n)	O(log n)
Linear search	O(1)	O(n)	O(1)

Recursive pays O(log n) in stack space. Best case is O(1) for both — the first mid might already be the answer.

Common Pitfalls

Most bugs are at the boundaries, not in the idea.

Forgetting to sort first. The algorithm assumes a sorted, totally-ordered sequence. Skip the sort, get garbage out.

Off-by-one with `<` vs `<=`. Using while left < right: when right = len(arr) - 1 silently skips the last element. The snippet above uses <= because right is an inclusive index. Pick one convention and stick to it.

Integer overflow on `(left + right) // 2`. A non-issue in Python (ints are unbounded), but real in C, C++, and Java. The defensive form left + (right - left) // 2 is a habit worth keeping for portability.

Infinite loops. Setting left = mid instead of left = mid + 1 (or right = mid instead of right = mid - 1) traps you on the same midpoint forever. Always exclude the midpoint once you've ruled it out.

Applying it to a linked list. Binary search needs O(1) random access. Walking to mid in a linked list is already O(n), which destroys the whole benefit.

Real-World Uses

Python's `bisect` module. A C-implemented binary search in the standard library. bisect_left, bisect_right, and insort give you ordered insertion and lookup with zero dependencies.

Database B-tree indexes. Postgres, MySQL, and SQLite all use B-tree / B+tree indexes — generalised binary search across disk pages. WHERE id = 42 is a tree-shaped binary search.

`git bisect`. When a bug appears and you don't know which commit broke it, git bisect walks your history binary-search style, asking you to mark each midpoint commit good or bad until it pinpoints the culprit.

Debugging by elimination. Comment out half the code, check if the bug persists, recurse.

Autocomplete. Sorted word lists plus a leftmost binary search give you the start of a prefix range in microseconds.

Inventory and pricing lookups. Sorted SKU tables and timestamp logs are all binary-searchable.

IP routing tables. Longest-prefix matching often uses binary search on prefix length.

Variants Worth Knowing

Leftmost / rightmost binary search. When duplicates exist, plain binary search returns some match. To get the first or last occurrence, keep searching after a match — push right = mid - 1 for leftmost, left = mid + 1 for rightmost.

`lower_bound` / `upper_bound`. These return the insertion point that keeps a list sorted — lower_bound is the first valid spot, upper_bound the last. Python's bisect_left and bisect_right are exactly these.

Search in a rotated sorted array. Given [6, 7, 0, 1, 2, 4, 5], find a target. At each step decide which half is still sorted, then check whether the target falls inside it. Still O(log n).

Binary search on the answer (parametric search). When a problem has a monotonic yes/no predicate — can we ship all packages within `k` days? — you binary search the answer space rather than an array. Turns gnarly problems into clean O(n log n) solutions.

Frequently Asked Questions

Why is binary search faster than linear search?

Linear search is O(n) — one comparison per item. Binary search is O(log n) — it discards half the candidates per comparison. For a million items, that's roughly 20 comparisons vs a million.

Does the array have to be sorted?

Yes, completely. The whole algorithm relies on the invariant that everything left of mid is <= arr[mid] and everything right is >=. Break it and the result is meaningless.

What if the array has duplicates?

Plain binary search returns some matching index — no guarantee which one. For first or last occurrence, use the leftmost / rightmost variant, or bisect_left / bisect_right.

Is `bisect` faster than my hand-written version?

Nearly always. bisect is written in C and skips Python interpreter overhead. Roll your own to learn — use bisect in production.

Can I binary search on floats?

Yes, and it's invaluable for things like square roots or finding a smallest feasible parameter. Loop a fixed number of times (say 100) or until right - left < 1e-9 instead of relying on equality, which rarely terminates cleanly with floats.

Can I use binary search on a linked list?

Not usefully. Reaching the midpoint already costs O(n) — no random access. Use a sorted array, balanced BST, or skip list instead.

Binary Search in Python

Try it yourself

How it works