Binary search without an off-by-one bug
Implement lower-bound binary search with a half-open interval, prove its boundaries, and test empty arrays, duplicates, and the insertion point after the last value.

A reliable binary search starts with a precise result: return the first index whose value is greater than or equal to the target, or return the array length if no such value exists. This operation is called a lower bound. If you have written a search that sometimes hangs on two elements or returns an arbitrary duplicate, this contract gives each boundary update a reason.
Assume the input is sorted in nondecreasing order and comparisons form a consistent ordering. The result is an insertion position, so it can be valid even when the target is absent. Searching [1, 2, 2, 2, 5] for two returns one. Searching the same array for four returns four. Searching for six returns five, one position beyond the last element.
Keep the uncertain interval half open
Use two boundaries, lo and hi, with the search interval written [lo, hi). The left endpoint belongs to the interval; the right endpoint does not. Everything before lo is known to be smaller than the target. Everything at or after hi is known to be greater than or equal to it.
def lower_bound(values, target):
lo, hi = 0, len(values)
while lo < hi:
mid = lo + (hi - lo) // 2
if values[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
assert lower_bound([], 2) == 0
assert lower_bound([1, 2, 2, 2, 5], 2) == 1
assert lower_bound([1, 2, 2, 2, 5], 4) == 4
assert lower_bound([1, 2, 2, 2, 5], 6) == 5
When values[mid] < target, sortedness tells you that every value through mid is too small. Moving lo to mid + 1 discards that entire region. Keeping lo = mid could leave a one-element interval unchanged and create an infinite loop.
Otherwise, mid could be the first qualifying position. Keep it available as the answer by moving hi to mid. Although mid leaves the uncertain interval, it becomes the first position in the region already known to qualify. That distinction explains why discarding it from the interval does not discard it as a possible boundary result.
Trace an input with duplicates
For [1, 2, 2, 2, 5] and target two, the first midpoint is two. Its value qualifies, so hi becomes two. The next midpoint is one, which also qualifies, and hi becomes one. The final midpoint is zero; its value is too small, so lo becomes one. Both boundaries now equal one.
Returning immediately on equality would stop at index two in this trace and violate the first-occurrence contract. The repeated equal values are not an awkward exception. They are what makes the distinction between finding any match and finding a boundary visible.
The invariant is true before the first iteration because both known regions are empty. Each update preserves its corresponding ordering claim. When lo == hi, there is no uncertain position between the known smaller values and the known qualifying values, so their shared boundary is the answer. Cornell’s loop-invariant notes give the general proof method for these search loops.
The interval length is a nonnegative integer that strictly decreases on each iteration. With lo < hi, the midpoint always lies inside the interval. Either update removes at least that midpoint, which proves termination even on one-element arrays.
Separate an insertion point from a successful lookup
To return the first matching index, run the lower-bound search and then check both the boundary and the value. The equality test alone is unsafe because the returned position can be the array length.
def first_index(values, target):
position = lower_bound(values, target)
if position < len(values) and values[position] == target:
return position
return None
assert first_index([1, 2, 2, 5], 2) == 1
assert first_index([1, 2, 2, 5], 3) is None
assert first_index([], 3) is None
Python supplies the insertion-point operation as bisect_left. Its documented partition is the same one used here. For ordinary application code, the library implementation avoids maintaining another copy of a boundary-sensitive loop.
The search performs O(log n) comparisons and uses O(1) auxiliary space. Inserting into a dynamic array at the returned position still requires shifting elements, which takes O(n) in the worst case. A fast way to find a position does not make editing the underlying representation equally fast.
Find the whole equal range with two boundaries
A lower bound finds the first value at least as large as the target. An upper bound finds the first value strictly larger. Only the comparison in the loop changes, but the contract explains why equality must now move the left boundary forward.
def upper_bound(values, target):
lo, hi = 0, len(values)
while lo < hi:
mid = lo + (hi - lo) // 2
if values[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def equal_range(values, target):
return lower_bound(values, target), upper_bound(values, target)
values = [1, 2, 2, 2, 5, 8, 8]
assert equal_range(values, 2) == (1, 4)
assert equal_range(values, 3) == (4, 4)
assert equal_range(values, 9) == (7, 7)
assert equal_range([], 2) == (0, 0)
The upper-bound invariant puts values less than or equal to the target before lo, and values strictly greater at or after hi. The same interval-shrinking argument proves termination. Python documents this second partition under bisect_right. Mixing the two partition statements while keeping the old equality branch is a common source of plausible but incorrect duplicate counts.
All occurrences of the target lie in [left, right) returned by equal_range, so their number is right - left. A missing target produces an empty interval at its insertion position. Neither endpoint must be a valid element index: both can equal the array length when the target is above every value. Counting needs only subtraction, without indexing either endpoint.
You can also count records whose keys lie in an inclusive value interval. The two endpoints have different roles: use a lower bound for the allowed minimum and an upper bound for the allowed maximum.
def count_inclusive(values, minimum, maximum):
if minimum > maximum:
raise ValueError('minimum exceeds maximum')
return upper_bound(values, maximum) - lower_bound(values, minimum)
assert count_inclusive(values, 2, 5) == 4
assert count_inclusive(values, 3, 4) == 0
assert count_inclusive([], 2, 5) == 0
On the example, the inclusive value range from two through five occupies indices one through four. Its half-open index interval is [1, 5), containing four records. Confusing an inclusive value endpoint with an inclusive index endpoint would count one extra record. Rejecting an inverted value range avoids returning a misleading negative count.
Each boundary search costs O(log n) comparisons, so two searches remain O(log n). Copying values[left:right] to return the matching records adds O(k) work and storage for k output elements in a Python list. A count-only API can avoid that copy. Reporting the search cost without the required output cost would describe a different operation.
For an exercise, check a target below all values, one equal to a duplicate run, and one between runs. Then compare the inclusive count with a direct predicate count on small sorted inputs. Keep the ordering guarantee and the meaning of both endpoints in the test description, so a one-character comparison change cannot silently change the requested result.
Test the ordering contract too
Empty input and a target outside both ends check boundary handling. Duplicate runs check whether the function really finds the left boundary. Arrays of one and two elements expose updates that fail to make progress. An exhaustive test can generate small sorted integer arrays and compare the result with the first index satisfying the predicate.
Floating-point NaN values violate the ordinary comparison expectations used in this proof. For example, both nan < x and nan >= x can be false. A list containing NaNs needs an explicit total ordering or a policy that rejects them before using this algorithm. Likewise, an array sorted case-insensitively must be searched with that same key rule.
Do not sort inside every lookup without accounting for that cost. If a caller promises a sorted array, keep that promise explicit and test the code responsible for maintaining it. When values change frequently, a different data structure may suit the workload. The lower-bound loop remains useful whenever a monotone false-then-true predicate lets you identify a boundary, including searches over answer values rather than stored array elements.