Учитывая массив целых чисел nums, отсортированных в порядке возрастания, найдите начальную и конечную позицию данного значения target.
Сложность вашего алгоритма во время выполнения должна быть порядка O(log n).
Если цель не найдена в массиве, вернуть [-1, -1].
Пример 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Пример 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Решение :
Итеративное решение простое, но требует O (n). Поскольку входные данные отсортированы, мы должны использовать модифицированный двоичный поиск, чтобы определить диапазон заданной цели.
- Выполните обычный бинарный поиск, чтобы выяснить, присутствует ли данная цель в массиве.
- Если цель существует, теперь выполните модифицированный двоичный поиск, чтобы определить низкий и высокий индекс цели.
