Algorithms and data structures · Introductory

Binary search: handle boundaries with a half-open interval

Maintain a shrinking candidate interval to search sorted arrays and locate insertion boundaries correctly.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Identify why half the candidates can be discarded
  2. Find a boundary in a duplicate-containing array
  3. Preserve an invariant while shrinking the interval
  4. Separate comparisons from the cost of access and insertion
  5. Trace a boundary-returning implementation
  6. Test termination with the invariant
  7. Ask Logeia about this articleCheck your understanding

Identify why half the candidates can be discarded

Binary search uses a comparison to remove roughly half of the remaining candidates. In an ascending array, if the middle value is below the target, every earlier value is also below it, so that whole part can be discarded. Sorted order, or another monotonic predicate, justifies the step. Running the same procedure on unsorted data is not valid because the target might lie in the discarded portion. Before writing the loop, state which property makes the search decision monotonic and which boundary the operation is intended to return.

Find a boundary in a duplicate-containing array

For [2, 4, 4, 7, 9], find the first position whose value is at least four. Use a half-open interval [lo, hi), beginning with lo = 0 and hi = 5. If the middle value is at least four, move hi to that position; otherwise, move lo one past the middle. When both boundaries meet, the answer is index one. Returning immediately on any equality would answer membership, but would not guarantee the first occurrence. Distinguish searching for an arbitrary matching item from finding a lower or upper boundary.

lohimidDecision and update
052Value ≥4, set hi=2
021Value ≥4, set hi=1
010Value <4, set lo=1
11—Done: return 1

Preserve an invariant while shrinking the interval

A lower-bound search can maintain that every position before lo is below the target and every position at or after hi is at least the target. The boundary hi may equal n, outside the last element, and the returned insertion position may also be n. An empty array begins with lo equal to hi at zero. With fixed-width integer arithmetic, a midpoint expression such as lo + (hi - lo) / 2 avoids overflowing their direct sum. Every branch must shrink the undecided interval to prevent off-by-one errors or an infinite loop.

python
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

Separate comparisons from the cost of access and insertion

On a random-access array, repeated halving gives logarithmically many comparisons and indexed reads. A linked structure may need substantial traversal just to reach a midpoint, so reducing comparisons does not automatically produce the same total-time bound. Finding an insertion position also does not perform the insertion itself: shifting a sorted array’s later elements can still take linear time. Test empty arrays, absent targets on either side, repeated equal values, and a one-element interval. Those cases directly exercise the boundary contract instead of only demonstrating a successful search in the middle.

Trace a boundary-returning implementation

The function below returns the first position whose value is at least target. For [2,4,4,7,9] and target 4, the half-open range changes from [0,5) to [0,2), [0,1), then [1,1), returning one. All positions before lo are below target, while positions at or after hi are at least target. A target of ten returns n, which is a valid insertion boundary but not an index to dereference. Membership additionally requires p<n and a[p]==target. The same implementation returns zero on an empty array; that is part of its defined boundary behavior.

Python
def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Test termination with the invariant

The interval length hi−lo must strictly shrink. Assigning lo=mid in the below-target branch can leave a one-element candidate interval unchanged forever. Reusing an old midpoint after changing a boundary is another error. Test targets below the first element, above the last element and inside repeated equal keys. In addition to checking selected example results, verify that every position left of the returned boundary is below target and every position to its right is at least target. This property checks the intended partition directly and exposes boundary mistakes that a few ordinary successful searches may miss.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path