Lower Bound и Upper Bound

Ищем границу, а не совпадение

Во многих задачах недостаточно узнать, встречается ли значение. Нужна позиция, с которой начинается определённая часть отсортированного массива. Для этого удобно использовать две стандартные границы.

• Lower bound — первая позиция, где значение не меньше target.
• Upper bound — первая позиция, где значение больше 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;
}

Здесь используется полуинтервал [left, right), поэтому правая граница изначально равна values.length. Если values[mid] уже не меньше цели, позиция mid всё ещё может оказаться первой подходящей, поэтому мы сохраняем её через right = mid.

Upper bound отличается одним условием

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;
}

Теперь все значения, равные цели, уходят в левую часть, поэтому итоговая позиция оказывается сразу после последнего target. Обе функции могут вернуть values.length, если подходящей позиции внутри массива нет.