Справа от вас
Алгоритмы поиска: бинарный поиск — метод II
Этот метод представляет собой расширенную форму бинарного поиска, используемого для поиска в массиве элемента или условия, для которого требуется:
доступ к текущему индексуИ индексу его непосредственного правого соседа.
Этот метод использует правого соседа элемента, чтобы определить, выполняется ли условие, и принять решение двигаться влево или вправо. Это также гарантирует, что доступный для поиска подраздел имеет размер не менее 2 на каждом шаге.
Правильно — отличительный синтаксис
- Исходное состояние:
left = 0, right = nums.length - Прекращение:
left === right - Поиск слева:
right = mid - Правильный поиск:
left = mid + 1
Правильно — постобработка
Как правило, Binary Search состоит из 3 основных разделов:
- Предварительная обработка.Сортировка, если коллекция не отсортирована.
- Двоичный поиск.Использование цикла или рекурсии для деления области поиска пополам после каждого сравнения.
- Постобработка.Определение подходящих кандидатов в оставшемся пространстве.
В отличие от Техники I, Техника II обычно требует постобработки. Поскольку цикл или рекурсия заканчивается, когда остается 1 элемент (left === right), вам необходимо оценить, соответствует ли оставшийся элемент условию. Другими словами: если элемент, удовлетворяющий условию, не возвращается из цикла или рекурсии, необходимо оценить оставшийся элемент (nums[left]), чтобы увидеть, он соответствует условию.
// Post-processing // End Condition: left === right if(left !== nums.length && nums[left] === target) return left return -1
Все правильные ходы
Пример JavaScript
Примеры проблем
📚 Ресурсы 👀
Leetcode Explore: Бинарный поиск — Шаблон II
Первая плохая версия | ЛитКод 278 | Учебное пособие по прохождению кода на Facebook
