Data Structures & Algorithms / Contracts, sequences, and search / Lesson 6

Binary search and boundary invariants

Derive lower-bound search from a partition invariant and handle duplicates and absence without guessing midpoint rules.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

Search needs a proven ordering precondition
Maintain a half-open unknown region
Halving counts comparisons, not all possible work

Search needs a proven ordering precondition

Binary search discards a large region only because ordering proves that region cannot contain the desired boundary. An unsorted sequence invalidates that reasoning even if selected examples happen to work. State the comparison key, direction, and duplicate policy. A lower bound returns the first position whose value is not less than the target, which can be the length when every value is smaller. It is an insertion boundary, not automatic evidence of membership. Comparing the value at that position requires a separate in-bounds and equality check.

Maintain a half-open unknown region

The first program maintains that all positions before lo contain values less than target and all positions at or after hi contain values at least target. Only [lo,hi) remains unknown. When values[mid] is smaller, mid and everything before it can be excluded by setting lo=mid+1. Otherwise mid remains a candidate boundary and hi=mid. Each iteration strictly shrinks hi-lo, proving termination. At lo==hi there is no unknown position and the partition boundary is established. This invariant explains the updates instead of relying on memorized plus-one patterns.

python Self-contained Python3 algorithm example using synthetic local data.

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

print(lower_bound([1, 3, 3, 8], 3))
print(lower_bound([1, 3, 3, 8], 9))
print(lower_bound([], 3))

Expected output

1
4
0

Duplicate3 values begin at index1. Target9 belongs after the last element, and the empty sequence has insertion boundary0.

Halving counts comparisons, not all possible work

The unknown interval approximately halves each iteration, giving logarithmic comparisons for random-access sorted data. On a linked structure, reaching the midpoint can require traversal, so copying the loop shape does not preserve the same access cost. Sorting an unsorted input first adds its own work and may be unnecessary for one lookup. Key extraction can also be expensive when repeated. Analyze preparation, comparisons, access, and output together under the selected representation. Python integers avoid fixed-width midpoint overflow, but lo+(hi-lo)//2 expresses the shrinking interval clearly and transfers to bounded-integer settings more safely.

Use paired boundaries for duplicate counts

The second program uses the standard bisect functions to locate the left and right boundaries of equal values. Their difference counts occurrences without scanning the entire equal run. The library returns insertion points and primarily uses ordering comparisons, not a generic equality-based membership search. The input must remain sorted and stable during the operation. Inserting at the boundary into a Python list can still move many elements, so insort is not a logarithmic total insertion merely because it finds its location logarithmically. Search cost and modification cost remain separate.

python Self-contained Python3 algorithm example using synthetic local data.

from bisect import bisect_left, bisect_right

def occurrences(values, target):
    return bisect_right(values, target) - bisect_left(values, target)

values = [1, 3, 3, 8]
print(occurrences(values, 3))
print(occurrences(values, 4))
position = bisect_left(values, 4)
print(position < len(values) and values[position] == 4)

Expected output

2
0
False

The insertion point for4 is valid as a boundary but does not mean4 exists. Paired boundaries correctly report zero occurrences.

Generalize only when the predicate is monotone

Boundary search can apply to a predicate that is false up to one boundary and true afterward, such as a documented feasibility threshold. Prove that monotonicity before using the pattern. Arbitrary success/failure observations are not sufficient, and negative weights can invalidate assumptions in some capacity problems. Define the search domain and ensure the answer exists or include an explicit not-found sentinel. Do not mix a closed interval proof with half-open updates. A boundary search is a theorem about a partition, not a trick that makes every numeric optimization logarithmic.

Check partition properties exhaustively on tiny inputs

Generate small nondecreasing arrays with duplicates and compare lower_bound against bisect_left or a direct linear reference. For each answer p, verify every earlier value is smaller than target and every later value is at least target. Include targets below all values, equal to repeated values, between values, and above all values, plus empty input. Check termination with shrinking interval reasoning rather than a timeout alone. These tests validate boundary behavior under the precondition; they do not make unsorted input valid. Keep precondition enforcement separate from the logarithmic search if checking sortedness would require a full scan.

Common errors and fixes

A search loops forever on two elements

Why it happens: The unknown interval does not strictly shrink in one branch.
How to fix it: Derive updates from the invariant and measure hi-lo.
Prevent it next time: Trace two-element and singleton intervals.

An insertion boundary is reported as membership

Why it happens: The returned index was never checked for equality and bounds.
How to fix it: Check index<len and the value comparison before claiming presence.
Prevent it next time: Test targets between values and above the maximum.

Binary search is applied to unsorted data

Why it happens: The partition precondition was assumed from one passing example.
How to fix it: Establish ordering or choose another algorithm.
Prevent it next time: Document sort key and input snapshot ownership.

Check your understanding

1. Why does the smaller-than-target branch move lo to mid+1?

Show worked solution

The tested midpoint is proved too small and cannot be the first value at least target. Excluding it preserves the left partition and guarantees progress. Leaving lo at mid can repeat the same midpoint when only two candidates remain.

2. Is bisect-based insertion into a Python list O(log n) overall?