Search Patterns

The classic binary search finds one element in a sorted array. That same idea — halve the search space at every step — works on a much wider class of problems once you recognize the underlying shape: a monotonic property (meaning the answer only ever moves in one direction as you increase the input — never flips back). This lesson covers four patterns that come up constantly in interviews and in production engineering code.

First and last occurrence — bisect_left vs bisect_right

Given a sorted array with duplicates, you often need the index of the first copy of a value, the last copy, or the count of copies. Python’s bisect module handles all three in two calls.

• bisect_left(a, x) returns the leftmost index where x could be inserted without breaking the sort order — the index of the first x if it exists.
• bisect_right(a, x) returns the rightmost such index — one past the last x.
• The count of x in a is therefore bisect_right(a, x) - bisect_left(a, x).

Data engineering angle. This pattern turns up constantly in timeseries work: bucket a timestamp into a pre-sorted list of interval boundaries, find the first event after a cutoff, or compute quantile positions without sorting the whole array again. Both bisect_left and bisect_right are O(log n) and operate on any sorted sequence.

Search in a rotated sorted array

A sorted array may be rotated at some pivot: [4, 5, 6, 7, 0, 1, 2]. There is no single rule that tells you “go left” or “go right” by comparing target with mid alone — but there is always one half that is fully sorted, and you can check whether the target falls inside it.

The idea:

1. Compute mid = (lo + hi) // 2.
2. If a[lo] <= a[mid], the left half is sorted. Check whether a[lo] <= target < a[mid]; if yes, narrow to [lo, mid). Otherwise, narrow to [mid+1, hi).
3. Otherwise, the right half is sorted. Check whether a[mid] < target <= a[hi]; if yes, narrow to [mid+1, hi]. Otherwise, narrow to [lo, mid).

The key insight: even after rotation, one of the two halves is always sorted. That is enough to make a binary decision at every step, keeping the algorithm O(log n).

Search in a 2D matrix

Given an m x n matrix where each row is sorted left-to-right and each column is sorted top-to-bottom, find a target value.

The staircase approach starts at the top-right corner — the one cell where moving left always decreases the value and moving down always increases it, giving a clean binary decision at every step — and exploits both sort orders simultaneously:

• If cell == target, done.
• If cell > target, move left (eliminate the entire column — nothing below can be smaller in this column).
• If cell < target, move down (eliminate the entire row — nothing to the left can be larger in this row).

Each step eliminates one row or one column, so the worst case is O(m + n).

Binary search on the answer

This is the most powerful generalization. Sometimes you cannot binary search the data itself — there is no sorted array of candidates. Instead, you binary search the answer space: you define a range [lo, hi] for the answer, pick the midpoint, and ask “is this answer feasible?” If the feasibility check is monotonic (once feasible, always feasible as the value grows, or the reverse), you can binary search it.

Classic example: minimum capacity to ship packages in D days.

You have a list of package weights. A ship with daily capacity C ships packages in order; a day’s shipment cannot exceed C. Find the minimum C such that all packages ship within D days.

• The answer space is [max(weights), sum(weights)] — capacity must be at least the heaviest package, and at most the total.
• Feasibility check: simulate greedily; count the days needed at capacity C. If days <= D, C is feasible.
• The feasibility function is monotonic: if C works, any larger C also works.

The same template appears in: smallest threshold above which a model passes a quality metric, minimum bandwidth to serve requests within latency budget, minimum number of machines for a distributed job. Anywhere the question is “what is the smallest X such that X is sufficient?” and “sufficient” is monotonic in X.

Quick check