Lower Bound and Upper Bound

Searching for a boundary, not a match

In many problems, knowing whether a value exists is not enough. What matters is the position where a particular part of the sorted array begins. Two standard boundaries are especially useful for this.

• Lower bound is the first position whose value is not less than target.
• Upper bound is the first position whose value is greater than target.

Lower bound

static int lowerBound(int[] values, int target) {
    int left = 0;
    int right = values.length;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (values[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

This template uses the half-open range [left, right), so the initial right boundary is values.length. If values[mid] is already not less than the target, position mid may still be the first suitable one, so it is preserved with right = mid.

Upper bound differs by one condition

static int upperBound(int[] values, int target) {
    int left = 0;
    int right = values.length;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (values[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

Now every value equal to the target is moved into the left part, so the final position is immediately after the last target. Both functions may return values.length when no suitable position exists inside the array.