Дан слайс целых чисел, отсортированный по неубыванию, и значение target.
Найдите индекс самого левого и самого правого вхождения target. Если
target в слайсе нет, верните -1, -1.
// SearchRange возвращает индексы первого и последнего вхождения target
// или -1, -1, если его нет.
func SearchRange(nums []int, target int) (first, last int)
Примеры
nums = [5, 7, 7, 8, 8, 10], target = 8 → 3, 4
nums = [5, 7, 7, 8, 8, 10], target = 6 → -1, -1
nums = [], target = 0 → -1, -1
nums = [2, 2, 2], target = 2 → 0, 2
Ограничения
0 ≤ len(nums) ≤ 10⁶, любые int, повторов может быть очень много.- Слайс менять нельзя.
- Ожидается O(log n) на запрос, независимо от числа повторов. Решение «найти
любое вхождение бинпоиском и расшириться влево-вправо» — O(n) на слайсе из
одинаковых чисел и не уложится по времени.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.