Просто хотите код? Прокрутите вниз до двух версий кода.
- Итеративный двоичный поиск
- Рекурсивный двоичный поиск
Что такое двоичный поиск?
Двоичный поиск - это алгоритм поиска, который находит местоположение целевого значения в отсортированном массиве с использованием подхода «разделяй и властвуй». Он работает, сравнивая целевое значение с серединой массива. Если оно не равно, найдите ту половину, где будет цель, и повторяйте этот процесс, пока не найдете целевое значение.
При поиске, чтобы проверить, существует ли элемент в массиве, наиболее распространенным методом грубой силы будет использование линейного поиска, поиск по каждому элементу от начального индекса до конца. По сравнению с этим двоичный поиск значительно превосходит линейный поиск, но работает только с отсортированными массивами.
Шаги по поиску с использованием двоичного поиска
- Сравните целевое значение со средним элементом массива.
- Если оно не равно, избавьтесь от половины, в которой целевое значение не может быть.
- Повторяйте шаги 1 и 2, пока не найдете ответ.
Двоичный поиск в JavaScript
Есть два способа кодирования двоичного поиска: итеративный с циклом while или с рекурсивной функцией. Концепция не меняется, всего нам нужно четыре переменных. Один для отслеживания массива (arr), другой - целевое значение (x), еще один для позиции начального индекса (start) и последний для отслеживания позиции конечного индекса (end).
Начните с создания цикла while, чтобы проверить, меньше ли начальный индекс конечному индексу или равен ему. Это используется, чтобы определить, существует ли искомое значение внутри массива или нет.
Внутри мы в основном находим средний индекс и сравниваем его с целевым значением. Если это значение, мы возвращаем индексное расположение значения. Если нет, мы проверяем, находится ли значение с левой стороны массива или с правой стороны.
Затем мы повторяем процесс, пока не найдем значение. Если мы не найдем значение, верните -1 в качестве позиции индекса, поскольку это недопустимая позиция индекса.
Двоичный поиск в JavaScript с рекурсией
Бинарный поиск с рекурсией ничем не отличается. Мы проверяем, проходит ли начальный индекс конечный. Если это так, это означает, что значение не существует в массиве.
Затем мы находим среднюю точку, сравниваем ее с целью и, если она равна, мы нашли нашу цель в массиве и теперь можем вернуть индекс.
Единственное, что отличается от рекурсивного, - это вместо того, чтобы просто обновлять начальное и конечное местоположение, мы вызываем там функцию с обновленной информацией.
Единственное, на что следует обратить внимание, это то, что при первом вызове рекурсивной функции вы должны вручную ввести начальный индекс как 0 и конечный индекс как длину массива минус один.
