Binary search needs an invariant and a precise boundary convention. For a lower-bound search, the task is to return the first position whose value is at least a target. The answer may be the length of the array if no value qualifies.

The example assumes nondecreasing, randomly accessible input. It uses a half-open interval: left is included and right is excluded.

How does a lower-bound search work?

def lower_bound(values, target):
    left, right = 0, len(values)
    while left < right:
        middle = left + (right - left) // 2
        if values[middle] < target:
            left = middle + 1
        else:
            right = middle
    return left

assert lower_bound([1, 3, 3, 7], 3) == 1
assert lower_bound([1, 3, 3, 7], 4) == 3
assert lower_bound([1, 3, 3, 7], 9) == 4
assert lower_bound([], 2) == 0
assert lower_bound([3, 3, 3], 3) == 0

Values before left are known to be below the target. Values at or beyond right are known to qualify, within the original array bounds. The unknown interval shrinks until left and right identify the boundary.

Why is right set to middle rather than middle minus one?

When the middle value qualifies, it could be the first qualifying position. Keeping it as the excluded right boundary preserves that possible answer while searching earlier positions. Subtracting one would use a different interval convention and can skip the desired boundary if mixed into this implementation.

Do not combine a loop condition from one binary-search template with update rules from another. Several correct forms exist, but their invariants must agree.

Why is left set to middle plus one?

If the middle value is below the target, every earlier value is also below the target because the array is sorted. Middle cannot be the answer, so the next unknown interval starts after it. The interval must get smaller on every iteration.

This explains both correctness and termination. If an update leaves the same interval when only one unknown position remains, the search can loop forever even though it appears to halve the range in larger examples.

How do duplicates change the answer?

A search for any matching value can stop at a middle match. Lower bound cannot: there may be an earlier equal value. That is why the qualifying branch continues searching towards the left boundary.

After obtaining the boundary, a caller can check whether it lies inside the array and whether the value equals the target. Lower-bound position and target existence are related but different results.

What should be said about complexity?

The number of comparisons grows logarithmically with the number of array elements because the remaining interval shrinks substantially each time. The shown implementation uses constant auxiliary state. If reaching the middle requires linear traversal, as in some linked structures, the access-cost analysis changes.

The midpoint expression avoids an addition that could overflow in fixed-width integer languages. Python integers have different overflow behavior, but explaining the expression helps when translating the algorithm to another language.

Which tests are most revealing?

  • An empty array and a one-value array.
  • A target below every value.
  • A target above every value.
  • A run of equal values at the beginning or end.
  • A target between two values with no exact match.

For practice, write a linear reference that counts values below the target and compare it with lower_bound on small sorted arrays. Then explain what would change for the first value strictly greater than the target. Changing one comparison changes the boundary's meaning; document that meaning before editing the code.

References and next practice

ocw.mit.edu — algorithms

Browse interview topics · Practise a question in Interview Challenge · How to Answer Technical Interview Questions Out Loud