Searching and Binary Search

From an O(n) scan to O(log n) halving — and past arrays, to searching the answer itself

Halve each stepO(log n) instead of a linear O(n) scan
lo <= hithe invariant that stops the classic off-by-one bug
Search the answerany monotonic condition, not just a literal array
bisect firsthand-roll the loop only when there is no real sorted sequence

1.Binary search on a sorted array — O(log n)

On a sorted array, compare the target to the middle element and throw away the half it cannot be in. Repeating that halves the search space every step, giving O(log n) instead of O(n).

Key features

Requires the input to already be sorted — binary search gives no warning if it is not, it just returns a wrong answer
O(log n) time, O(1) extra space for the iterative version shown below
lo and hi are both valid indices to check; the loop keeps going while lo <= hi, and stops once the search space is empty

Binary search only works on sorted data — it never checks that precondition itself, so passing unsorted data gives a wrong answer with no error.

2.Writing binary search without off-by-one bugs (lo, hi, mid, loop invariant)

The invariant is: "if the target exists, it is somewhere in nums[lo..hi]". Every line has to protect that invariant — the loop condition, and both branches that move lo or hi.

Key features

Use lo <= hi, not lo < hi — with lo < hi, the case where exactly one candidate remains (lo == hi) never gets checked at all
Move lo to mid + 1 and hi to mid - 1, never to mid itself — once nums[mid] has been ruled out, leaving it in the range risks an infinite loop
In Python, mid = (lo + hi) // 2 never overflows — ints have arbitrary precision, so the classic C/Java overflow bug that motivates lo + (hi - lo) // 2 does not apply here

The invariant is "the target, if present, is in nums[lo..hi]" — while lo <= hi keeps a single remaining candidate in play, and mid + 1 / mid - 1 keep a ruled-out mid from ever coming back.

3.Binary search on the answer

Binary search does not need a literal array — it works on any range of candidate answers where a yes/no condition flips exactly once from false to true. Search that range instead of the input.

Key features

Requires a monotonic condition: once it becomes true for some X, it must stay true for every value beyond X (or the mirror image for false)
The search space is a range of integers (or a precision-bounded range of floats), not the input array itself
Recognize it from phrasing like "minimum X such that Y is possible" or "smallest capacity/speed/size that satisfies a condition"

Whenever a problem asks for the minimum/maximum value satisfying a yes/no condition that flips exactly once, binary search the range of possible answers — get the boundary condition (<= vs <) exactly right, since it decides whether the true answer itself is accepted.

4.Binary search on a rotated sorted array

A rotated sorted array is still sorted in two pieces. At any mid, one of the two halves (nums[lo..mid] or nums[mid..hi]) is guaranteed to be in normal sorted order — check that half first.

Key features

At least one of the two halves around mid is always normally sorted — the rotation point can only be in one of them
nums[lo] <= nums[mid] means the LEFT half is the normal sorted one; otherwise the RIGHT half is
Still O(log n) — each step still discards half of the remaining search space, exactly like ordinary binary search

Use nums[lo] <= nums[mid] (not strict <) to decide which half is sorted — a one-element left half has nums[lo] == nums[mid], and it is still trivially sorted.

5.Binary search for exact match vs "leftmost/rightmost occurrence"

On a sorted array with duplicates, plain binary search returns SOME index holding the target — not necessarily the first or last one. Finding a specific boundary needs a small change: keep narrowing even after a match, instead of returning immediately.

Key features

On a match, do not return immediately — record the index, then keep searching the left half (hi = mid - 1) for leftmost, or the right half (lo = mid + 1) for rightmost
Which index a plain binary search lands on among duplicates depends on the exact sequence of mid values — treat it as arbitrary, never as "the first one"
Python's bisect_left and bisect_right give the leftmost and rightmost insertion points directly — see algorithms.searching-and-binary-search.bisect-bisect-left-and-bisect-right

A match is not automatically the answer when duplicates exist — record it, then keep narrowing in the direction (left for leftmost, right for rightmost) that could still improve it.

6.Search in a 2D sorted matrix

When a matrix is sorted along every row and every column, it can be treated as one long sorted list of rows * cols elements — binary search it directly using index math to convert between a flat position and a (row, col) pair.

Key features

Only applies when the matrix is fully sorted (each row's first element is greater than the previous row's last) — a matrix sorted only within rows, not across them, needs a different approach (binary search each row, or a staircase walk from a corner)
mid // cols recovers the row, mid % cols recovers the column — the same math used to flatten a 2D grid into 1D anywhere else
Still O(log(rows * cols)) — the same complexity as a 1D binary search over all the elements

A fully sorted matrix is one sorted list in disguise — binary search it with mid // cols and mid % cols standing in for the row and column.

7.`bisect.bisect_left` / `bisect.bisect_right`

bisect_left finds the leftmost position where a value could be inserted and keep the list sorted; bisect_right finds the rightmost such position. The gap between them is exactly the count of that value in the list.

Key features

Both run in O(log n) — they are the standard library's own binary search, not something to hand-roll for a plain sorted-position lookup
The list must already be sorted — like every binary search, bisect gives no warning if it is not
bisect_right(a, x) - bisect_left(a, x) equals the number of times x appears in a — a fast way to count occurrences without scanning

bisect_left is the leftmost valid insertion point, bisect_right is the rightmost — reach for the gap between them whenever you need to count a value in a sorted list.

8.bisect.insort for maintaining a sorted list

bisect.insort finds the correct sorted position for a value and inserts it there in one call, so the list never needs a full re-sort after adding an element.

Key features

O(n) overall — O(log n) to find the position, O(n) to shift elements to make room — NOT O(log n) like the search alone
Keeps the list sorted incrementally, one insert at a time, instead of calling sorted() or .sort() after every addition
For workloads that insert far more often than they search, a different structure (like a heap) can beat repeated insort — see algorithms.heaps-and-priority-queues

insort keeps a list sorted after every insert, in O(n) per call — cheaper than re-sorting from scratch, but still not O(log n), because shifting elements to make room is unavoidable in a plain list.

Spotted a mistake on this page? Tell us.

Read Sheet