Binary search with a boundary invariant
Why you care
Most binary search bugs are boundary bugs: an off-by-one that loops forever, or an answer one slot too far left. In ETL work the same code appears as "first row at or after the watermark" or "how many events fall in this hour" on a sorted extract. Get the boundary wrong and you double-load one row or drop one, silently. Interviewers ask for binary search because it is short enough to write in five minutes and strict enough that a missing invariant shows at once.
Explain like I'm 5
You want the first page of a phone book where surnames reach "Mehta" or later. Open the middle. If that page is still before "Mehta", throw away the left half. If it is "Mehta" or later, it might be your answer, so keep it and discard only what lies to its right. Every opening discards at least one page, never one that could still be the answer.
Core concept
Write the question as one sentence first: find the first index whose element satisfies a condition that flips from false to true once. For plain search the condition is xs[i] >= target.
- Use a half-open interval
[lo, hi)withhi = len(xs), so "insert at the end" is a legal answer. - Loop while
lo < hi;mid = (lo + hi) // 2is always< hi, soxs[mid]is safe. - Fails the condition:
lo = mid + 1. Passes:hi = mid. Both shrink the interval, so it terminates; everything left oflofails and everything fromhipasses. - Lower bound (
bisect_left) is the firstx >= t; upper bound (bisect_right) is the firstx > t. Their difference counts copies oft. - Exact match is search plus a post-check:
i < len(xs) and xs[i] == t.
Use it when data is sorted (or the condition is monotone) and you need a position, a range count or an insertion point. Do not use it on unsorted data, and do not call insort in a hot loop: the search is O(log n) comparisons but the list shift is O(n). bisect accepts key= from Python 3.10, applied to list elements, not to the value you search for.
Minimal example Left versus right, and the end slot
from bisect import bisect_left, bisect_right
a = [1, 3, 3, 3, 7]
print(bisect_left(a, 3), bisect_right(a, 3))
print(bisect_left(a, 9), len(a))
print(bisect_left(a, 0))
i = bisect_left(a, 4)
print(i, i < len(a) and a[i] == 4)1 4
5 5
0
4 FalseIn production Hand-written lower bound checked against bisect
The sorted guard matters: binary search on unsorted input returns a confident wrong number, not an error.
from bisect import bisect_left
def lower_bound(xs, target):
"""First index i with xs[i] >= target, or len(xs). Search space is [lo, hi)."""
lo, hi = 0, len(xs)
while lo < hi:
mid = (lo + hi) // 2
if xs[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def count_in_window(ts, start, end):
"""Events with start <= t < end, two boundary searches and a subtraction."""
if any(a > b for a, b in zip(ts, ts[1:])):
raise ValueError("timestamps must be sorted ascending")
return lower_bound(ts, end) - lower_bound(ts, start)
def find_exact(xs, t):
i = lower_bound(xs, t)
return i if i < len(xs) and xs[i] == t else -1
settled = [100, 100, 130, 130, 130, 175, 200, 200, 260]
for t in range(90, 270):
assert lower_bound(settled, t) == bisect_left(settled, t), t
print("matches bisect_left on 180 targets")
print(count_in_window(settled, 100, 200))
print(count_in_window(settled, 130, 131))
print(count_in_window(settled, 261, 300))
print(count_in_window(settled, 0, 10**9))
print(find_exact(settled, 175), find_exact(settled, 176), find_exact(settled, 999))
try:
count_in_window([5, 3, 9], 0, 10)
except ValueError as e:
print(f"ValueError: {e}")matches bisect_left on 180 targets
6
3
0
9
5 -1 -1
ValueError: timestamps must be sorted ascendingSee it happen The interval shrinks, hi never passes the answer
- Start with lo=0 and hi=5, one past the last item, so the search space is [0, 5).
- mid=2 holds 3, which is not below the target, so it may be the answer and hi moves onto it.
- mid=1 holds 3 again, so hi moves left to 1 and the duplicate to its right is discarded safely.
- mid=0 holds 1, below the target, so lo steps past it to 1.
- lo equals hi at 1: that is the first element that is 3 or more, and the post-check xs[1] == 3 confirms a match.
hi only lands on a slot that passed the test, so the leftmost duplicate is never lost.In your world
The situation
Your Jenkins job loads incremental extracts from S3, sorted by updated_at, and must start at the first row at or after the last watermark. Today it reads everything and filters in a Python loop.
What actually breaks
A teammate hand-rolls a search with hi = len(rows) - 1 and while lo < hi. When the watermark equals the last timestamp it lands one slot early and one row loads twice. Counts drift by 1 per file until finance notices.
What you'd do on Monday
Use bisect_left on a key list and test three edges: watermark before, at and after the last row.
from bisect import bisect_left
stamps = [r["updated_at"] for r in rows] # sorted by contract
start = bisect_left(stamps, watermark) # first row >= watermark
new_rows = rows[start:] # len(rows) means "nothing new"Imagine you work at Microsoft
The numbers
Illustrative: 2,000,000,000 keys × 16 bytes ≈ 32 GB. A linear scan at ~1 GB/s costs ≈ 32 s per lookup. Binary search needs ⌈log2(2×10^9)⌉ = 31 probes; at ~100 µs per random SSD read that is 31 × 100 µs ≈ 3.1 ms.
What the Scenario-A answer does here
The Scenario A fix works while the array fits in RAM. At 32 GB each of the 31 probes is a cold page read.
What flips at this scale
Make the top of the search permanent. Keep one key per 4 KB page in memory: 32 GB ÷ 4 KB = 8M pages × 16 B ≈ 128 MB. Search that index in RAM, then do one page read and a local search. The same invariant now runs at two levels.
The trade-off you'd defend
I would defend a sparse in-memory index plus one page read over pure on-disk bisection, trading 128 MB of RAM and a rebuild on writes for about 30x fewer random reads.
Illustrative numbers chosen to show the arithmetic; not Microsoft-published figures.
Gotchas
Search loops forever or skips the answer
The call never returns, or returns an index one slot too small on exact-boundary inputs.
Closed bounds (hi = n - 1) mixed with half-open moves (hi = mid), or lo = mid without + 1, so the interval stops shrinking.
Pick half-open [lo, hi) once; use only lo = mid + 1 or hi = mid.
Insertion point read as a match
IndexError: list index out of range on xs[i], or "found" for an absent value.
bisect_left returns len(xs) past the end.
Post-check i < len(xs) and xs[i] == target.
Tricky questions
bisect_left or bisect_right?Either one, since both find where the value is.
Neither alone. The count is bisect_right(a, t) - bisect_left(a, t).
Scenario question
You're handed 50 million sorted order timestamps and asked for the order count in each of 24 hourly windows.
Model answer
I would do two bisect_left calls per window: about 24 × 2 × 26 ≈ 1,250 comparisons instead of 24 scans of 50 million rows. The trade-off is that I depend on the sort contract; if upstream delivers unsorted data the counts are silently wrong, so I would sample-assert at load.
Interview corner
CommonWrite binary search and state your invariant.
hi starts at len(xs). Everything left of lo is below the target and everything from hi on is at or above it. Both updates shrink the interval, so it terminates with lo as the answer.”TrickWhat does bisect_left return if the target exceeds everything?
len(a) back, the insertion point at the end, so I always post-check i < len(a) before indexing.”Experience checkWhere have you used sorted data to avoid a scan?
bisect_left instead of filtering every row, and I tested watermark before, inside and after the data.”Memory hook
A phone book where you only throw away pages that cannot be the answer.
Define the false-to-true boundary first, keep [lo, hi) half-open, and post-check an exact match.
Self-check
What does
bisect_right(a, t) - bisect_left(a, t)give?The number of occurrences of
t.Why start
hiatlen(xs)?The answer may be the end slot, and half-open intervals make that normal.
What does
insortcost, and why?O(n): the search is O(log n) but the list shift is linear.
Compare your lower_bound and upper_bound with bisect_left and bisect_right on 10,000 seeded random sorted lists with duplicates, for every target from min - 1 to max + 1. Paste the zero-mismatch line.