Boundary searches

Ask a slightly different question

Finding any matching value is sometimes enough. Other times you need the first value greater than or equal to the target. This position is called a lower bound.

For [2, 5, 5, 5, 8] and target 5, the lower bound is index 1. For target 6, it is index 4. For target 9, it is index 5: the position just after the array.

A half-open interval

Use the interval [low, high), which includes low but excludes high. Initially, low = 0 and high = a.length.

• Indices below low contain values smaller than the target.
• Indices at or above high contain values greater than or equal to the target.
• The unresolved region lies between them.

static int lowerBound(int[] a, int target) {
    int low = 0;
    int high = a.length;

    while (low < high) {
        int mid = low + (high - low) / 2;
        if (a[mid] < target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

When a[mid] equals the target, keep mid as a possible answer by setting high = mid. Earlier matches may still exist.

Interpreting the result

The returned position may equal the array length. Check bounds before indexing:

int position = lowerBound(a, target);
boolean found = position < a.length && a[position] == target;

An empty array returns 0. A target larger than every element returns a.length. Both are valid insertion positions.

Try it yourself

Trace the method for [2, 5, 5, 5, 8] and target 5. Record each interval.