Turn every boundary search into “find the first index where a monotonic predicate is true” over a half-open range [lo, hi). Keep mid when the predicate holds, discard it when it fails, and stop when lo == hi. One template and one invariant replace off-by-one guesswork.
Reframe the problem as the first true predicate
Picture the search space as a row of booleans: False, False, then True, True. Binary search works whenever such a monotonic predicate exists, sorted array or not. The function below keeps one invariant: every index below lo is False, every index at or above hi is True, and the answer lies in [lo, hi]. When pred(mid) is true, mid might be the first true, so hi = mid keeps it. When it is false, lo = mid + 1 discards it.
The output lines are 3 1 1 4, then 4 4 4 4, 10 6 6 6, and 0 0 0 0. For the predicate x ≤ a[i], first_true matches bisect_left on every query, and bisect_right gives the first index whose value exceeds x. When nothing is true, the function returns hi, which equals len(a): the insertion point at the end. The last line, 4, is first bad version with the predicate 4 ≤ v over versions 1 to 5.
from bisect import bisect_left, bisect_right
def first_true(lo, hi, pred):
"""Smallest i in [lo, hi) with pred(i) true, or hi if there is none.
pred must be monotonic: False ... False True ... True."""
while lo < hi:
mid = (lo + hi) // 2
if pred(mid):
hi = mid # mid may be the answer: keep it inside
else:
lo = mid + 1 # mid is ruled out
return lo
a = [1, 3, 3, 3, 7, 9]
for x in (3, 4, 10, 0):
mine = first_true(0, len(a), lambda i: x <= a[i])
print(x, mine, bisect_left(a, x), bisect_right(a, x))
first_bad = 4 # versions 1..5, bad from 4 onward
print(first_true(1, 6, lambda v: first_bad <= v))Why half-open intervals remove a class of bugs
In a 1982 note, Dijkstra argued for writing ranges as lo ≤ i < hi: the length is hi − lo, adjacent ranges share a bound, and an empty range needs no unnatural bounds, just lo == hi. Binary search inherits all three benefits. The loop condition is lo < hi, the range shrinks on every iteration because lo ≤ mid < hi, and the function always has an answer to return, even for an empty input.
C++ uses the same convention. std::lower_bound returns the first element in [first, last) that is not ordered before the value, or last if there is none, and cppreference notes that the range only needs to be partitioned with respect to the comparison, not fully sorted. That is the monotonic predicate idea in library form, with a documented cost of at most log₂(N) + O(1) comparisons.
The classic off-by-one bugs, reproduced
A classic infinite loop pairs lo = mid with a mid that rounds down. When hi = lo + 1, mid equals lo, the assignment changes nothing, and the loop never ends. The script looks for the last value below 5 in [1, 2, 4, 8]. Rounding down hits the step guard and prints stuck at lo=2, hi=3; rounding up prints 2. A simpler fix is to avoid the last-true form entirely: compute first_true for x ≤ a[i] and subtract one.
The other classic is overflow. In 2006 Joshua Bloch reported that the JDK's binary search computed (low + high) / 2, which overflows int once arrays reach about a billion elements; his post gives low + ((high - low) / 2), or an unsigned right shift of low + high by one bit, as fixes. Python integers do not overflow, so (lo + hi) // 2 is safe in Python, but mention the issue in a Java or C++ interview.
def last_below(a, x, round_up, max_steps=20):
"""Index of the last a[i] < x. Assumes a[0] < x <= a[-1]."""
lo, hi = 0, len(a) - 1
for _ in range(max_steps):
if lo == hi:
return lo
mid = (lo + hi + 1) // 2 if round_up else (lo + hi) // 2
if a[mid] < x:
lo = mid # keeps mid, so mid must differ from lo
else:
hi = mid - 1
return f"stuck at lo={lo}, hi={hi}"
a = [1, 2, 4, 8]
print(last_below(a, 5, round_up=False))
print(last_below(a, 5, round_up=True))| Bug | Symptom | Fix |
|---|---|---|
| lo = mid with mid rounded down | Infinite loop when hi = lo + 1 | Round up, or use first_true minus 1 |
| while lo <= hi with hi = mid | Infinite loop once lo == hi | Use lo < hi with hi = mid |
| hi = len(a) - 1 in a boundary search | Cannot report that nothing matched | Start with hi = len(a) |
| (low + high) / 2 on int | Negative index on huge arrays | low + (high - low) / 2 |
| Using the result without checks | IndexError when it equals len(a) | Check i < len(a) and a[i] == x |
Search in a rotated sorted array
After rotation, [4, 5, 6, 7, 0, 1, 2] is no longer sorted, but at any mid at least one of the two halves is. If a[lo] <= a[mid], the left part is sorted and you can test whether the target lies inside its range; otherwise the right part is sorted. Each step discards half, so the search stays O(log n). This version uses a closed interval and lo <= hi because it looks for an exact match and returns as soon as it finds one.
The script prints [4, 0, 6, -1] for targets 0, 4, 2, and 3, then True after checking every rotation of a seven-element array against list.index for 24 targets. The distinct-values assumption is load-bearing. With duplicates, a[lo] == a[mid] no longer reveals which side is sorted: on [1, 2, 1, 1, 1] this code assumes the left part is sorted and returns -1 for target 2. The duplicate-safe fix shrinks both ends by one when they tie, so the worst case degrades to O(n). Ask whether duplicates are allowed before you start.
def search_rotated(a, target):
"""a: ascending distinct values, rotated. Returns index or -1."""
lo, hi = 0, len(a) - 1 # closed interval: exact match
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
return mid
if a[lo] <= a[mid]: # left part a[lo..mid] is sorted
if a[lo] <= target < a[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right part a[mid..hi] is sorted
if a[mid] < target <= a[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
a = [4, 5, 6, 7, 0, 1, 2]
print([search_rotated(a, t) for t in (0, 4, 2, 3)])
base = list(range(0, 21, 3))
rotations = [base[s:] + base[:s] for s in range(len(base))]
print(all(search_rotated(r, t) == (r.index(t) if t in r else -1)
for r in rotations for t in range(-1, 23)))Binary search on the answer: minimum shipping capacity
Ship packages in their given order within d days and find the smallest ship capacity. There is no array to search, but there is a monotonic predicate: if capacity c finishes in d days, any larger capacity does too. The answer lies between max(weights), because the heaviest package must fit, and sum(weights), which ships everything in one day. Search that range with the same template, using a greedy days_needed check as the predicate.
For weights 1 through 10 and d = 5 the script prints 15 [6, 5]: capacity 14 needs six days and 15 needs five, so 15 is the boundary. The second case prints 6. The cost is O(n log S), where S is the sum of the weights, because each of about log₂ S probes scans the array once. The last line repeats the search with bisect_left over a range and a key function, and also prints 15.
from bisect import bisect_left
def days_needed(weights, cap):
days, load = 1, 0
for w in weights: # greedy: fill a day until w won't fit
if cap < load + w:
days, load = days + 1, 0
load += w
return days
def ship_within_days(weights, d):
lo, hi = max(weights), sum(weights) # hi is always feasible
while lo < hi:
mid = (lo + hi) // 2
if days_needed(weights, mid) <= d:
hi = mid
else:
lo = mid + 1
return lo
w = list(range(1, 11))
print(ship_within_days(w, 5), [days_needed(w, c) for c in (14, 15)])
print(ship_within_days([3, 2, 2, 4, 1, 4], 3))
caps = range(max(w), sum(w) + 1) # bisect over a lazy range, 3.10+
print(caps[bisect_left(caps, True, key=lambda c: days_needed(w, c) <= 5)])When to reach for Python's bisect
In Python, bisect_left and bisect_right are the tested versions of lower and upper bound. Their documented contract is a partition: everything before the returned index is less than x (or at most x, for bisect_right), and everything from it onward is not. They compare with __lt__ only and never call __eq__, so you still check a[i] == x yourself. Since Python 3.10 both accept key=, which is how the answer search above runs over a lazy range.
In an interview, ask whether library calls are allowed. If they are, bisect shows judgment; if not, write first_true and mention that it matches bisect_left. One trap: insort keeps a list sorted, but the documentation points out that its O(log n) search is dominated by the O(n) insertion step, so n insort calls can cost O(n²) overall, not O(n log n).
A practice plan for binary search problems
Pick problems by predicate type rather than by site: boundaries in a sorted array (first and last position of a value), implicit predicates (first bad version, integer square root), rotated or partitioned arrays, and answer searches (shipping capacity, eating speed, splitting an array into k parts). Before coding each one, write the predicate, the range, and why the predicate is monotonic. Then test one- and two-element ranges, where off-by-one bugs live.
For related material, the data structures and algorithms set covers neighboring topics, and the 30-day study plan schedules pattern practice across a month.
Quick answers
Frequently asked questions
Should I use lo <= hi or lo < hi?
Use lo < hi with a half-open range for boundary searches, because the loop ends with lo == hi as the answer. Use lo <= hi with a closed range for exact-match searches that return from inside the loop. Mixing the two conventions is a frequent source of infinite loops.
How do I know a problem is binary search on the answer?
Look for wording such as “minimum capacity” or “smallest value such that,” plus a feasibility check you can write in linear time. If feasibility at x implies feasibility at every larger x, the answer is the first true point of that predicate.
Does binary search require a sorted array?
It requires a partitioned search space: a predicate that is false and then true. A sorted array provides that for comparisons with a target, but rotated arrays, version histories, and capacity ranges provide it too.
What does bisect_left return when the value is missing?
The insertion point, where x would go to keep the list sorted. For [1, 3, 3, 3, 7, 9] and x = 4 it returns 4, and for a value larger than every element it returns len(a). Check the index and the value before using it.
Source notes
References and review policy
Information checked on November 7, 2026. Section links identify sources for factual claims and technical explanations. Interpretations, practice scenarios and preparation recommendations are RecallDeck’s editorial work.
From reading to recall
Practice the full interview loop.
RecallDeck schedules the concepts you miss and keeps coding, design, and behavioral fundamentals available when the interviewer changes direction.