Алгоритмы поиска: линейный и двоичный

Поиск — это нахождение нужного элемента в наборе или выяснение того, что его там нет. Самый простой способ — линейный поиск: элементы проверяют по одному с начала, и как только нужный найден, поиск останавливается. Он работает в любом списке, но в худшем случае приходится просмотреть все n элементов. В Python для списка x in a и a.index(x) работают именно так.

Двоичный поиск работает только в упорядоченном массиве. Он сравнивает искомое число со средним элементом: если искомое меньше, правая половина отбрасывается, если больше — левая. С оставшейся частью действие повторяют, поэтому на каждом шаге область поиска сокращается примерно вдвое. Средний индекс вычисляют по формуле mid = (low + high) // 2.

Будем искать 23 в упорядоченном массиве 2 5 8 12 16 23 38 56 72 91. На 1-м шаге средний элемент 16 меньше искомого, поэтому поиск продолжается в правой половине (23 38 56 72 91). На 2-м шаге средний элемент 56 больше, значит, остаётся левая часть (23 38); на 3-м шаге средний элемент равен 23 — число найдено.

При линейном поиске число сравнений пропорционально числу элементов, а при двоичном — не более примерно log2 n. Например, в упорядоченном массиве из 1 000 000 элементов двоичный поиск выполнит не больше 20 шагов, а линейный — до миллиона сравнений. Однако если массив сначала нужно отсортировать, для одного поиска проще линейный метод; при многократном поиске выгодно один раз отсортировать массив, а затем использовать двоичный метод.

Главное

• Линейный поиск проверяет элементы по одному и работает в любом списке.
• Двоичный поиск работает только в упорядоченном массиве.
• Двоичный поиск на каждом шаге сокращает область поиска примерно вдвое.
• На 1 000 000 элементов двоичный поиск делает не более 20 шагов, а линейный — до миллиона сравнений.
• Перед многократным поиском выгодно один раз отсортировать массив.