Binary Search (Бинарный поиск)
Описание: Дан отсортированный по возрастанию массив nums и число target. Верните индекс target, если он есть в массиве, иначе верните -1.
Пример 1:
Вход: nums = [-1,0,3,5,9,12], target = 9
Выход: 4
Объяснение: Число 9 стоит на позиции 4
Пример 2:
Вход: nums = [-1,0,3,5,9,12], target = 2
Выход: -1
Объяснение: Числа 2 в массиве нет
Ограничения:
1 <= nums.length <= 10⁴
Массив отсортирован по возрастанию
Все значения уникальны
Рекомендуемая временная и пространственная сложность
Стремитесь к решению за O(log n) по времени и O(1) по памяти.
Подсказка 1
Линейный поиск даст O(n). Массив отсортирован — используйте это.
Подсказка 2
Сравните середину отрезка с целью. Если середина меньше — ответ правее, иначе левее.
Подсказка 3
Внимательно с границами: цикл идёт пока left <= right, а середину считайте как left + (right - left) / 2, чтобы избежать переполнения.