Search for a boundary, not just a match
In a sorted array, finding an occurrence of a value may not answer the actual question. If the value appears several times, we might need its first position, the position after its last occurrence, or the number of occurrences. If it is absent, an insertion position is still useful.
Definition 12.1.1
(Lower bound and upper bound)
Let be integers in nondecreasing order and let be an integer. The lower bound is the first index with , or if no such index exists. The upper bound is the first index with , or if no such index exists. Both results lie in ; is a valid boundary but is not an array index.
The values equal to occupy the half-open interval . Its length is their number. This remains true when is absent: the interval is empty, with .
Maintain what is already known
def lower_bound(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
The sorted integer array and random-access indexing are preconditions. The code does not sort or validate its input. At the start of every loop iteration, we maintain
The elements whose relation to is not yet settled lie in . The answer boundary itself remains in the inclusive range : is a possible answer even though it is not an element of the unknown interval. The empty ranges at the initial values make both value claims true without reading any element. There is no requirement to read .
Theorem 12.1.2
(Correctness of the lower-bound loop)
Let be integers, with , and let be an integer. The displayed invariant holds at every test of the condition . When the loop ends, lower_bound(a, x) returns the lower bound of in .
Proof
(Initialization, preservation and the final boundary)
Initially the bounds and both empty-range claims hold. While , the integer midpoint satisfies , so exists.
If , sortedness gives for all . Setting therefore extends the known-less-than region without invalidating the other region. Otherwise , and sortedness gives for all . Setting extends the known-at-least region. In each branch the bounds remain valid.
When the loop ends, . Every earlier element is less than , and every element at or after that position is at least . If the position equals , the latter region is empty and no element qualifies. Thus the returned position is exactly the specified lower bound, including for an empty array.
Proof X-ray
Where sortedness is used and why the updates are asymmetric
Sortedness is used exactly twice, once in each branch, and only in this form: one comparison at settles every index on one side of . In an unsorted array, would say nothing about for .
The two updates are asymmetric on purpose. If , the index is itself settled as "less than ", so may discard it. If , the index is settled as "at least ", but it may be the first such index; hence is set to and stays available as a possible answer.
The argument closes because the unknown interval is empty exactly when . The two settled regions then cover with no gap and no overlap, and the common boundary is the first index with .
The invariant also makes the insertion property clear: inserting at preserves sorted order. If equal elements already exist, that insertion is before all of them.
Proposition 12.1.3
(Upper bound and the number of equal entries)
For integers in nondecreasing order, the upper bound of equals the lower bound of . The entries equal to occupy exactly the positions in , so there are of them.
Proof
(Upper bound as a lower bound of the next integer)
For integers, is equivalent to , so the first index satisfying one condition is the first index satisfying the other. For the second claim, every index has and every index has , so neither can hold the value . For , we have because and sortedness, and because ; hence .
Concept lensCombinatorial
The boundary as a count
In a sorted array the entries below form an initial segment, so the lower bound is simply how many entries are below :
For and these are , and . Binary search computes this count without visiting every entry, because each comparison decides a whole block of indices at once.
Worked example 12.1.4
(A repeated value gives two useful boundaries)
For and , the lower-bound loop runs:
| lo | hi | mid | a[mid] | action |
|---|---|---|---|---|
| 0 | 5 | 2 | 2 | hi = 2 |
| 0 | 2 | 1 | 2 | hi = 1 |
| 0 | 1 | 0 | 1 | lo = 1 |
It returns . For the upper bound, replace the test a[mid] < x by a[mid] <= x and leave the rest unchanged. The successive intervals are , , and , so . The equal entries are positions 1, 2 and 3; their count is .
With the same array and , both bounds equal 4. There is no match, but inserting 3 at position 4 preserves the ordering.
Worked example 12.1.5
(Boundary cases: an empty array and a value above every entry)
For the empty array, and the initial interval is , so the loop body never runs and the function returns after zero comparisons.
Now take and .
| lo | hi | mid | a[mid] | action |
|---|---|---|---|---|
| 0 | 3 | 1 | 3 | lo = 2 |
| 2 | 3 | 2 | 5 | lo = 3 |
Both tests have , so moves to and the loop stops with two comparisons. The returned value is a correct answer: no element is at least . It is a boundary, not an index, and is never read.
Worked example 12.1.6
(A search that uses the maximum number of comparisons)
Let , so , and let .
| lo | hi | mid | a[mid] | action |
|---|---|---|---|---|
| 0 | 10 | 5 | 12 | lo = 6 |
| 6 | 10 | 8 | 18 | hi = 8 |
| 6 | 8 | 7 | 16 | hi = 7 |
| 6 | 7 | 6 | 14 | hi = 6 |
The interval lengths are . The function returns , and is indeed the first entry at least . Four comparisons were used, which equals the bound derived below.
Termination and cost
At each iteration, belongs to the nonempty unknown interval. Either the new interval is or it is ; both are strictly shorter. Thus the nonnegative integer decreases until termination.
Theorem 12.1.7
(Termination and comparison count of the lower-bound loop)
Let the unknown interval have length at the start of an iteration. After the iteration its length is at most . Consequently the loop terminates after at most iterations for , and after none for . Each iteration makes one comparison.
Proof
(Halving the unknown interval)
The midpoint is , and . If becomes , the new length is . If becomes , the new length is . Let be the maximum number of iterations from length . Then and for . By induction, for : for it is , and for we have .
The theorem gives comparisons at most for , and an empty array takes zero. With constant-time random access and integer comparisons, the time is and the auxiliary space is . These are not guarantees about a linked list whose indexed access must walk from the head, expensive comparisons, or the cost of initially sorting an unsorted input.
In fixed-width arithmetic, lo + (hi - lo) // 2 avoids adding two potentially large indices, provided the nonnegative bounds and their difference fit the chosen index type. Python integers do not overflow, but an implementation in another language still needs appropriate index types.
A common boundary error
Counterexample mode
Mixing an inclusive loop with an exclusive upper boundary
Suppose the code starts with hi = len(a) but uses while lo <= hi, retaining the same midpoint access. For and , the first comparison sets lo=1. The next iteration tries to read a[1], which is outside the array. The number is a possible answer, not a readable element.
Inclusive and half-open formulations can both be correct, but their initial bounds, loop conditions, updates and proofs must match. Merely changing one symbol in an otherwise correct version does not preserve the invariant.
Common mistake
(Treating the returned boundary as proof that x is present)
The lower bound is defined whether or not occurs. If , then does not exist; if , it may be that . For and the result is , but . Membership holds exactly when and , equivalently when .
Common mistake
(Reading the upper bound as the last occurrence)
The upper bound is the position after the last equal entry. For and it is , while the last occurrence is at index . This formula is valid only when ; for an absent value, may be a smaller value or, if , not an index at all.
Exercises with solutions
Quick check
(For , find the lower and upper bounds of and of .)
Use the definition: the first index satisfying the condition, or if none does.
Solution · Answer
For both bounds are . For both are , the array length. Neither case reads a sentinel element.
Quick check
(What do the lower and upper bounds return for and ?)
Count the entries equal to with .
Solution · Answer
They return and . Their difference is the number of equal entries.
Quick check
(Why does the lower-bound algorithm set hi = mid, not hi = mid - 1, when ?)
Ask whether itself could be the answer.
Solution · Answer
The midpoint itself may be the first qualifying position. Keeping it as the end of the unknown interval preserves that possibility. For and , the first midpoint is , but subtracting one sets hi=0 and incorrectly returns .
Quick check
(A programmer uses the upper-bound test and obtains . Is it safe to inspect ?)
Recall which values of are indices.
Solution · Answer
No. means no element is greater than ; the last valid index, when the array is nonempty, is .
A proof of a search routine must describe the answer's contract, the known regions, and the exact treatment of boundaries. The short loop is reliable because each update preserves those meanings.