Первая и последняя позиция

Повторы превращают поиск в задачу о границах

В отсортированном массиве одинаковые значения стоят рядом. Поэтому все вхождения target образуют один непрерывный диапазон. Его начало можно найти через lower bound, а конец — через upper bound.

static int[] firstAndLast(int[] values, int target) {
    int first = lowerBound(values, target);

    if (first == values.length || values[first] != target) {
        return new int[] {-1, -1};
    }

    int last = upperBound(values, target) - 1;
    return new int[] {first, last};
}

Сначала мы находим первую позицию со значением не меньше цели. Если она вышла за массив или на ней лежит другое число, значит, target вообще отсутствует. Иначе первый индекс уже известен.

Почему upper bound нужно уменьшить на один

Upper bound указывает на первую позицию со значением больше цели. Следовательно, последнее вхождение target находится непосредственно перед этой границей. Именно поэтому используется upperBound(values, target) - 1.

Сложность не меняется

Мы запускаем два бинарных поиска, каждый за O(log n). Суммарно это всё ещё O(log n), потому что постоянное число логарифмических проходов не меняет асимптотику.