Двоичный поиск
Двоичный поиск быстро находит элемент в упорядоченном массиве: на каждом шаге проверяется средний элемент, после чего половина диапазона отбрасывается.
Как работает
Сначала задаются левая и правая границы диапазона. Вычисляется средняя позиция \(m=\left\lfloor\frac{l+r}{2}\right\rfloor\). Если средний элемент равен искомому, поиск завершён. Если он меньше искомого, левая граница сдвигается вправо: \(l=m+1\). Если он больше, правая граница сдвигается влево: \(r=m-1\). Поиск продолжается, пока \(l\le r\).
Логарифмическая сложность означает, что число проверок растёт медленно. Например, для массива из 1 000 элементов потребуется не более примерно 10 делений диапазона. Это важный приём оптимизации алгоритма.
В массиве \([3, 7, 12, 18, 25, 31, 40]\) ищем число 31. Средний элемент — 18, поэтому отбрасываем левую половину. В оставшемся диапазоне средний элемент — 31, значит, искомое значение найдено за две проверки.
Линейный поиск проверяет элементы по очереди и не требует сортировки. Двоичный поиск работает быстро только тогда, когда массив уже упорядочен. Если массив не отсортирован, сравнение со средним элементом не позволяет правильно отбросить половину диапазона.
В отсортированном массиве из 32 элементов двоичный поиск выполняет не более какого порядка числа проверок?
Главное
- Двоичный поиск применяется к отсортированному массиву и каждый раз делит диапазон пополам.
- Границы изменяются по результату сравнения со средним элементом.
- Сложность двоичного поиска — \(O(\log n)\), что быстрее последовательного просмотра большого массива.