Простой способ поиска элемента в массиве - пройти по каждому элементу в массиве, пока не найдете целевой элемент. Это можно сделать, используя базовый цикл for для перебора массива. Хотя этот подход легко реализовать, он может быть не самым оптимальным. Когда мы работаем с массивом, который отсортирован в порядке возрастания или убывания, существует гораздо лучший метод, который может значительно сократить время выполнения.
Обычный способ описания бинарного поиска - поиск кого-либо в телефонной книге. Если бы мы искали Джо Смита, мы не стали бы искать по каждому имени с самого начала, пока не нашли Джо Смита. Более оптимальным подходом было бы открыть книгу до середины и начать оттуда. Скажем, середина привела нас к фамилиям, начинающимся с буквы М. Теперь мы знаем, что мы можем игнорировать первую половину книги, потому что Смит идет после М. Теперь мы берем последнюю половину книги и снова находим середину. Скажем, это подводит нас к букве R. Мы снова не обращаем внимания на первую половину оставшихся имен, находим середину и повторяем, пока не найдем Джо Смита.
Чтобы представить оптимизацию двоичного поиска в перспективе, давайте рассмотрим пример поиска элемента в списке из 1000 записей. Если мы используем простой обход, а записи оказались в конце списка, в худшем случае нам пришлось бы перебирать все 1000 записей. Используя двоичный поиск, мы сокращаем количество поисков до 10 в худшем случае. Это резкое снижение! Сначала берем 1000, разрезаем пополам до 500. Затем разрезаем от 500 до 250 и так далее. Чем больше увеличивается номер исходного списка, тем эффективнее становится двоичный поиск. Допустим, мы увеличили количество элементов с 1000 до 1000000. В худшем случае для этого потребуется всего 20 поисков.
Большой O
Если бы мы выразили эту оптимизацию в терминах Big O, мы бы сказали, что сокращаем время выполнения в худшем случае с O (n) до O (log n). Базовый обход потенциально может потребовать повторения каждого отдельного элемента. Следовательно, время выполнения увеличивается пропорционально количеству элементов. При двоичном поиске количество оставшихся элементов постоянно уменьшается вдвое, поэтому это описывается как log2 n (логарифм в степени 2), который в программировании чаще всего называют «log n». Это в основном обратное экспоненциальному росту.
Выполнение
Вот как можно реализовать двоичный поиск по массиву в Javascript. Сначала нам нужно создать 3 указателя. Один в начале массива, один в конце массива и один в середине. Средний элемент можно вычислить, сложив указатели начала и конца, разделив сумму на 2, а затем используя функцию Math.floor, чтобы округлить число до ближайшего целого числа.
Отсюда мы можем использовать цикл while, чтобы проверить, нашел ли средний указатель целевой элемент. Если нет, то мы проверяем, больше ли середина цели или меньше нее. Если оно больше, мы меняем конечный указатель на текущее среднее значение и вычитаем 1. Если оно меньше, мы меняем передний указатель на текущее среднее значение и добавляем 1. Затем мы пересчитываем среднее значение на основе наших новых начальных и конечных указателей.
В этом примере мы возвращаем индекс целевого элемента, если он найден, или возвращаем -1, если массив не содержит целевой элемент.
В следующий раз, когда вы создадите функцию для поиска элемента в массиве и у вас будет возможность работать с отсортированным массивом, используйте этот подход, чтобы воспользоваться преимуществом экспоненциального уменьшения времени выполнения.
