Overview
Curated: · Written: · Reviewed:
Binary search
Binary search is the algorithm most engineers can describe and fewest can write correctly on the first attempt, and the reason is that the code is not the technique — the containment invariant is. This guide treats binary search as the search for a boundary in a monotone predicate, of which searching a sorted array is one case and searching an answer space is another. It covers the half-open convention that removes most off-by-one errors, the midpoint overflow that shipped in real standard libraries, the leftmost and rightmost boundary variants that duplicates require, rotated arrays, floating-point termination, and the comparator contract whose violation returns a wrong answer rather than an error.
the halving argument
Binary search is logarithmic because each comparison eliminates half the remaining candidates, and it is correct only if that elimination is sound.
The search maintains a range known to contain the answer if it exists anywhere, and each step shrinks that range while preserving the containment property.
Thirty probes reach any element of a billion; the range must contain the answer at every step.
# Invariant: if target is present, it lies in a[lo:hi].
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < target: lo = mid + 1 # a[:mid+1] cannot contain it
else: hi = mid # a[mid+1:] cannot contain it
Interview trap. Describing binary search as 'guess the middle and adjust' omits the containment invariant, which is exactly what the tricky variants get wrong.
Engineering practice. Write down what the current range means before writing the loop, and check that each branch preserves it.
the monotonic-predicate formulation
Binary search applies to any predicate that is false for a prefix of the domain and true for the rest, whether or not an array is involved.
The search finds the boundary between the two regions, so the array formulation is the special case where the predicate is 'the element is at least the target'.
Nothing needs to be sorted in memory: the predicate supplies the order.
def feasible(capacity): ... # False, False, ..., False, True, True, ...
lo, hi = 1, max_capacity
while lo < hi:
mid = lo + (hi - lo) // 2
if feasible(mid): hi = mid
else: lo = mid + 1
return lo # the smallest feasible capacity
Interview trap. Restricting the technique to sorted arrays misses the whole class of answer-space searches where nothing is sorted in memory at all.
Engineering practice. State the predicate and prove its monotonicity before searching; if the predicate flips more than once, the technique does not apply.
half-open ranges
Using a half-open range keeps the loop condition, the midpoint, and the termination consistent and eliminates most off-by-one errors.
With the high bound exclusive, the range is empty exactly when the bounds are equal, the midpoint never equals the high bound, and the final position is the answer's insertion point.
With hi exclusive, the empty range is lo == hi and the result is the insertion point.
lo, hi = 0, len(a) # hi is exclusive
while lo < hi: # empty exactly when lo == hi
...
return lo # insertion point, in [0, len(a)]
Interview trap. Mixing an inclusive high bound with a half-open update rule produces a loop that either skips the last element or never terminates.
Engineering practice. Pick one convention, write it in a comment above the loop, and use it everywhere so the variants stay comparable.
midpoint overflow
Computing the midpoint by adding the bounds overflows in fixed-width integer languages, which is a real defect that shipped in widely used libraries.
Computing low plus half the difference stays within range for any valid pair of indices, and costs nothing extra.
(lo + hi) // 2 overflowed a real Java standard library for nine years.
mid = lo + (hi - lo) // 2 # safe for any valid pair of indices
mid = (lo + hi) // 2 # in a 32-bit language, overflows past 2^31 - 1
Python's integers are arbitrary precision, so write the safe form anyway - the habit transfers.
Interview trap. Assuming the inputs are too small to overflow is exactly the reasoning that left the bug in production standard libraries for years.
Engineering practice. Always compute the midpoint as low plus half the span, even in languages with arbitrary-precision integers, so the habit transfers.
termination
A binary search terminates only if the range strictly shrinks on every iteration.
With integer division the midpoint rounds towards the low bound, so a branch that sets low to the midpoint rather than past it can leave the range unchanged and loop forever.
Integer division rounds down, so lo = mid with an inclusive hi can loop forever.
# a = [1, 2], lo = 0, hi = 1: mid = 0. If the branch sets lo = mid, nothing changes.
while lo < hi:
mid = lo + (hi - lo) // 2
if cond(mid): hi = mid # strictly shrinks: hi < old hi
else: lo = mid + 1 # strictly shrinks: lo > old lo
Interview trap. Testing on a few inputs is not evidence of termination, because the non-shrinking case only occurs at specific range sizes.
Engineering practice. Verify that each branch strictly reduces the range, and if one cannot, change the midpoint's rounding direction to match.
leftmost and rightmost boundaries
With duplicates present, plain binary search returns an arbitrary matching index, and finding the first or last match requires a different comparison.
Searching for the leftmost match treats equality as 'go left' and searching for the rightmost treats it as 'go right', so the loop finds a boundary rather than a member.
Equality goes left for the first match and right for the last.
import bisect
a = [1, 2, 2, 2, 3]
bisect.bisect_left(a, 2) # 1 - first index where 2 could be inserted
bisect.bisect_right(a, 2) # 4 - one past the last 2
Interview trap. Finding any match and then scanning outwards is correct but degrades to linear time when the array is largely one repeated value.
Engineering practice. Use the boundary variants directly, and name which one the caller needs rather than returning an unspecified match.
insertion points
The standard library's bisect operations return insertion points, and the two variants differ only in where they place a value equal to an existing element.
The left variant returns the index of the first element not less than the target, and the right variant returns the index after the last element equal to it, which makes their difference the count of equal elements.
The gap between the two variants is exactly the count of equal elements.
a = [1, 2, 2, 2, 3]
bisect.bisect_right(a, 2) - bisect.bisect_left(a, 2) # 3
bisect.bisect_right(a, 9) - bisect.bisect_left(a, 9) # 0 - absent, not negative
Interview trap. Choosing the variant by trial rather than from the definition gives code that is right until the array contains duplicates.
Engineering practice. Prefer the library function to a hand-written loop, and derive the variant from what the code does with the returned index.
counting occurrences
The number of elements equal to a value is the difference between the two insertion points, computed in logarithmic time.
Both boundaries are independent binary searches, so the total remains logarithmic and no scan over the equal run is needed.
Two logarithmic searches beat scanning outwards from a hit.
def count(a, x):
return bisect.bisect_right(a, x) - bisect.bisect_left(a, x)
# On [5] * 1_000_000 this is 2 x 20 probes; scanning outwards is 1,000,000 steps.
Interview trap. Scanning outwards from a found index is the intuitive approach and is linear in the number of duplicates.
Engineering practice. Use two boundary searches, and check the case where the value is absent, which must yield a count of zero rather than a negative span.
searching a rotated sorted array
A rotated sorted array is still searchable in logarithmic time because at least one half of any range is properly sorted.
Comparing the midpoint with an endpoint identifies the sorted half, and the target is then either inside that half's range or in the other half.
Compare the midpoint with an endpoint to find the sorted half.
def search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if a[mid] == target: return mid
if a[lo] <= a[mid]: # left half is sorted
if a[lo] <= target < a[mid]: hi = mid - 1
else: lo = mid + 1
else: # right half is sorted
if a[mid] < target <= a[hi]: lo = mid + 1
else: hi = mid - 1
return -1
search([4, 5, 6, 7, 0, 1, 2], 0) # 4
Interview trap. Deciding the sorted half by comparing the midpoint with the target rather than with an endpoint gives a rule that fails on many rotations.
Engineering practice. Identify the sorted half first, then test containment against its two endpoints, and cover the unrotated and fully rotated cases in tests.
duplicates break the rotation argument
When a rotated array may contain duplicates, the worst case degrades to linear because the sorted half can no longer always be identified.
When the endpoints and the midpoint are equal, neither half is known to be sorted, and the only sound response is to narrow the range by one.
On [2, 2, 2, 0, 2] neither half is identifiable and the bound degrades to O(n).
if a[lo] == a[mid] == a[hi]:
lo += 1; hi -= 1 # the only sound move - one element at a time
Interview trap. Claiming logarithmic time for the duplicate-tolerant version is wrong, and an input of all-equal values demonstrates it immediately.
Engineering practice. State the degraded bound when duplicates are possible, and say which input achieves it.
finding the rotation point
The minimum of a rotated sorted array is the unique position where the order breaks, and it is found by comparing the midpoint with the high end.
If the midpoint exceeds the high element, the break is to the right; otherwise the break is at the midpoint or to its left, so the high bound moves to the midpoint rather than past it.
Compare with the high end; comparing with the low end fails on an unrotated array.
lo, hi = 0, len(a) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] > a[hi]: lo = mid + 1
else: hi = mid # mid may be the minimum, so keep it
# [1, 2, 3] -> 0; [3, 4, 5, 1, 2] -> 3
Interview trap. Comparing against the low end instead gives a rule that fails when the array is not rotated at all.
Engineering practice. Compare with the high end, keep the high bound inclusive of the midpoint, and test the already-sorted input.
binary search on the answer
When the answer is a number and feasibility is monotone in it, search the answer range rather than the input.
Each candidate answer is checked by a feasibility function, so the cost is the logarithm of the answer range times the cost of one check.
Search the capacity, not the array; each candidate costs one feasibility pass.
def days_needed(weights, cap):
days, load = 1, 0
for w in weights:
if load + w > cap: days += 1; load = 0
load += w
return days
lo, hi = max(weights), sum(weights) # both bounds provably safe
while lo < hi:
mid = lo + (hi - lo) // 2
if days_needed(weights, mid) <= limit: hi = mid
else: lo = mid + 1
Cost is O(n log(sum)) - about 30 passes for a sum near a billion.
Interview trap. Assuming the technique needs a sorted array excludes minimum-capacity, minimum-time, and rate-allocation problems where nothing is sorted.
Engineering practice. Define the feasibility predicate, argue its monotonicity, and bound the answer range explicitly before searching it.
choosing the answer range
The bounds of an answer-space search must be provably safe: the low bound infeasible or minimal, and the high bound certainly feasible.
A high bound that is not feasible makes the search return it without any check having succeeded, which is silently wrong.
The high bound must be feasible by construction, not by looking large.
lo = max(weights) # any smaller capacity cannot carry the heaviest item
hi = sum(weights) # one day carries everything: certainly feasible
Picking hi = 10_000 because it looks big returns 10,000 unchecked when the true answer exceeds it.
Interview trap. Picking a round number as the upper bound because it looks large enough is how these solutions fail on the largest test case.
Engineering practice. Derive both bounds from the problem's constraints, and assert feasibility of the upper bound in a test.
binary search on floating-point ranges
Searching a continuous range terminates on a precision target or a fixed iteration count, not on equality.
A fixed number of iterations — around a hundred for double precision — reduces the interval below any useful tolerance and cannot loop forever.
A fixed 100 iterations divides the interval by 2^100; equality never arrives.
lo, hi = 0.0, 1e9
for _ in range(100): # not `while lo < hi`
mid = (lo + hi) / 2
if feasible(mid): hi = mid
else: lo = mid
return hi # accurate to ~1e-21 of the original range
Interview trap. Looping while the bounds differ never terminates, because floating-point subtraction stops making progress before the bounds compare equal.
Engineering practice. Use a fixed iteration count or an absolute-and-relative tolerance, and state the precision the answer is guaranteed to.
the comparison function contract
Binary search assumes a total order consistent with the array's sort order, and violating that assumption gives undefined results rather than an error.
If the comparator is inconsistent — not transitive, or not matching the order the array was sorted with — the elimination step discards the region containing the answer.
Search with the key the array was sorted by, or the elimination discards the answer.
people.sort(key=lambda p: p.age)
bisect.bisect_left([p.age for p in people], 30) # correct
bisect.bisect_left([p.name for p in people], "x") # nonsense: that list is not sorted
Python 3.10+ accepts bisect_left(people, 30, key=lambda p: p.age), which keeps the pairing in one place.
Interview trap. Searching an array sorted by one key using a comparator on another key returns a plausible wrong answer with no exception raised.
Engineering practice. Search with the same comparator the array was sorted by, and encode the pairing so the two cannot drift apart.
when sorting first is not worth it
Sorting to enable binary search costs O(n log n), which only pays off when many searches share the sorted order.
A single lookup is cheaper as a linear scan, and a hash structure answers repeated point lookups in expected constant time without the ordering cost.
One lookup: scan. Many lookups: sort once, outside the loop.
# Wrong: 1,000 sorts of 1,000,000 elements
for q in queries: data.sort(); bisect.bisect_left(data, q)
# Right: one sort, then 1,000 logarithmic probes
data.sort()
[bisect.bisect_left(data, q) for q in queries]
Interview trap. Sorting inside a function called once per query converts a linear scan into a linearithmic sort repeated per call.
Engineering practice. Sort once outside the query loop, or choose a hash index when order is not otherwise needed.
binary search versus hashing
Hashing wins on point lookups, and binary search wins on ordered queries — predecessor, successor, and range.
A sorted array supports 'the smallest element greater than x' directly, which a hash structure cannot answer without scanning everything.
A set cannot answer 'the smallest element greater than x' at all.
| Query | set | sorted list + bisect |
|---|---|---|
| x present? | O(1) expected | O(log n) |
| smallest element > x | O(n) scan | O(log n) |
| range [lo, hi) | O(n) scan | O(log n + k) |
| ordered iteration | not supported | free |
Interview trap. Choosing by lookup cost alone leads to a hash structure that then needs a full scan for every range query.
Engineering practice. Choose from the full query mix, and if any query is ordered, keep the order.
cache behaviour and interpolation search
Binary search's memory access pattern is scattered, which is why its constant factor is worse than the asymptotics suggest for large arrays.
Each probe lands in a different cache line and there is a dependent load between steps, so the search cannot be prefetched; interpolation and B-tree-shaped layouts exist to fix this.
Logarithmic comparisons, but each probe is a likely cache miss.
# 1,000,000 x 8 bytes = 8 MB, far past L2. Each of the ~20 probes lands in a
# different cache line, and the next address depends on the previous load,
# so the hardware cannot prefetch any of them.
Interview trap. Assuming logarithmic comparisons means logarithmic wall time ignores that a cache miss can dominate a comparison by two orders of magnitude.
Engineering practice. For very large in-memory arrays, consider a cache-friendly layout or a wider branching structure, and measure rather than assume.
searching a two-dimensional sorted matrix
A matrix sorted by row and column is searched from a corner in linear time in the dimensions, not by binary search over the whole grid.
Starting from the top-right, a value larger than the target eliminates the column and a smaller one eliminates the row, so each step removes an entire line.
The staircase walk is O(rows + cols); per-row binary search is O(rows log cols).
r, c = 0, len(m[0]) - 1 # start top-right
while r < len(m) and c >= 0:
if m[r][c] == target: return True
if m[r][c] > target: c -= 1 # eliminate a column
else: r += 1 # eliminate a row
return False
Interview trap. Applying binary search per row is correct but costs a logarithmic factor per row, which is worse when the matrix is tall.
Engineering practice. Use the staircase walk when both dimensions are sorted, and flatten to a single binary search only when the matrix is fully sorted in row-major order.
the median of two sorted arrays
The median of two sorted arrays is found by binary searching the partition point of the shorter array.
A partition is valid when every element on the left of both arrays is at most every element on the right, which is a monotone predicate in the split position.
Search the partition of the shorter array; infinite sentinels remove the edge cases.
INF = float("inf")
left_a = a[i - 1] if i > 0 else -INF # empty partition
right_a = a[i] if i < len(a) else INF
# valid when left_a <= right_b and left_b <= right_a
Cost is O(log(min(m, n))) - about 10 probes for a 1,000-element shorter array.
Interview trap. Merging the arrays first is correct but linear, which misses the point of the question.
Engineering practice. Search the shorter array's partition, handle empty partitions with infinite sentinels, and cover the odd and even total-length cases separately.
the logarithm's base and practical depth
Binary search reaches any element of a billion-element array in about thirty comparisons, which is the intuition behind why the technique matters.
Each step halves the range, so the number of steps is the base-two logarithm of the size, rounded up.
Doubling the data adds one probe.
| Elements | Probes |
|---|---|
| 1,000 | 10 |
| 1,000,000 | 20 |
| 1,000,000,000 | 30 |
Interview trap. Optimising a binary search's comparison count is almost never where the time goes; the surrounding work usually dominates.
Engineering practice. Establish the number of comparisons before optimising, and check whether the comparator or the memory access is the real cost.
searching over an implicit array
The array being searched need not exist in memory — a function from index to value is enough.
This is what lets binary search run over a sorted stream, a paged remote dataset, or a computed sequence, at the cost of one evaluation per probe.
Thirty probes are cheap in memory and expensive over a network.
def value_at(i): return fetch(i) # one network round trip per probe
# 30 probes x 40 ms = 1.2 s. A single bulk fetch of the page may beat it outright.
Interview trap. Ignoring the per-probe cost matters when each evaluation is a network call, since thirty round trips may be worse than one bulk fetch.
Engineering practice. Cost the probe, not just the number of probes, and switch to a bulk strategy when each evaluation is expensive.
off-by-one testing strategy
The defects in binary search cluster at the boundaries, so the tests must be chosen there rather than randomly.
The revealing cases are the empty array, one element, the target below all elements, above all elements, at each end, and absent between two present values.
Test exhaustively at tiny sizes against a linear scan; that is where the defects live.
for n in range(0, 12):
a = sorted(random.choices(range(6), k=n))
for t in range(-1, 7):
assert bisect.bisect_left(a, t) == sum(1 for v in a if v < t)
Interview trap. Random testing against a linear scan finds these eventually, but only property-based testing across all small sizes finds them reliably.
Engineering practice. Test exhaustively for sizes zero to a few dozen against a brute-force reference, which covers every boundary the implementation can have.
using the library implementation
Hand-written binary searches are a known source of defects, and the standard library version is correct, tested, and usually faster.
The library variants cover leftmost, rightmost, and key-extracting forms, which is the majority of what applications need.
bisect is tested, C-accelerated, and takes a key function since 3.10.
import bisect
bisect.insort(a, x) # keeps a sorted, O(n) move but O(log n) search
bisect.bisect_left(records, 30, key=lambda r: r.age) # Python 3.10+
Interview trap. Rewriting the search to add a key function, when the library already accepts one, replaces tested code with untested code for no benefit.
Engineering practice. Reach for the library first, and hand-write only when the predicate is not expressible as an ordering on elements.
recognising the pattern
Binary search applies whenever there is a monotone predicate over an ordered domain, and the domain need not be the input.
The three recurring forms are searching a sorted array, searching a boundary among duplicates, and searching the answer space of a feasibility question.
Look for a monotone yes/no question, not for the word 'sorted'.
| Question | Monotone predicate |
|---|---|
| Where does x belong in a sorted array? | a[i] >= x |
| Smallest ship capacity to finish in d days | days_needed(cap) <= d |
| Minimum time to make n items | produced(t) >= n |
| Largest k with sum(a[:k]) <= budget | prefix(k) <= budget |
Interview trap. Looking for the word 'sorted' in the problem statement misses the answer-space form entirely, which is where the harder instances live.
Engineering practice. Ask what quantity has a monotone yes-or-no answer; if one exists, the logarithmic solution follows from it.