Анализ алгоритмов быстрого поиска в словаре

1.4. Бинарный поиск.
Бинарный поиск представляет собой в высшей степени эффективный алгоритм для поиска в отсортированном массиве. Он работает путем сравнения искомого ключа К со средним элементом массива А[m]. Если они равны, алгоритм прекращает работу. В противном случае та же операция рекурсивно повторяется для первой половины массива, если К < А[m], и для второй, если К > А[m]:

Хотя ясно, что бинарный поиск основан на рекурсии, его очень легко
реализовать как не рекурсивный алгоритм. Вот псевдокод не рекурсивной версии.

Стандартный способ анализа эффективности бинарного поиска состоит в подсчете количества сравнений искомого ключа с элементами массива. Кроме того, из соображений простоты, мы будем считать, что используются тройные сравнения, т.е. что одно сравнение К и А[m] позволяет определить, меньше ли К, больше или равно значению А[m]. Что можно сказать об эффективности бинарного поиска в среднем? Сложный анализ показывает, что среднее количество сравнений ключей в случае бинарного поиска только немного меньше такового в наихудшем случае: C(n) ≈ . (Более точные формулы для среднего количества сравнений в случае успешного и неудачного поиска — C(n) ≈ — 1 и С(n) ≈ , соответственно.)
Если ограничиться только операцией сравнения ключей, то бинарный поиск является оптимальным алгоритмом, однако имеются алгоритмы поиска с лучшим временем работы в среднем, а один из этих алгоритмов (хеширование) даже не требует, чтобы массив был отсортирован! Однако эти алгоритмы, кроме сравнения ключей, требуют некоторых специальных вычислений.


1.5. Интерполяционный поиск.
В качестве следующего примера алгоритма с переменным уменьшением размера задачи мы рассмотрим еще один алгоритм поиска в отсортированном массиве, который называется интерполяционным поиском (interpolation search). В отличие от бинарного поиска, который всегда сравнивает ключ поиска со средним значением отсортированного массива (а следовательно, всегда уменьшает размер задачи вдвое), интерполяционный поиск учитывает значение ключа поиска при определении элемента массива, который будет сравниваться с ключом.
Говоря более строго, при выполнении итерации поиска между элементами А[l] (крайним слева) и А[r] (крайним справа), алгоритм предполагает, что значения в массиве растут линейно (отличие от линейности может влиять на эффективность, но не на корректность данного алгоритма). В соответствии с этим предположением, значение v ключа поиска сравнивается с элементом, индекс которого вычисляется (с округлением) как координата х точки на прямой, проходящей через (l, А[l]) и (r, А[r]), координата у которой равна значению v. Записав стандартное уравнение для прямой, проходящей через две точки (l, А[l]) и (r, А[r]), заменив в нем у на v и решая его относительно х, получим формулу

Логика, лежащая в основе этого метода, проста. Мы знаем, что значения массива возрастают (точнее говоря, не убывают) от А[l] до А[r], но не знаем, как именно. Пусть это возрастание — линейное (простейшая из возможных функциональных зависимостей); в таком случае вычисленное по ранее записанной формуле значение индекса — ожидаемая позиция элемента со значением, равным v. Конечно, если v не находится между А[l] и А [r], формулу применять не следует.
После сравнения v с А[х] алгоритм либо прекращает работу (если они равны), либо продолжает поиск тем же способом среди элементов с индексами либо от l до х - 1, либо от х + 1 до r, в зависимости от того, меньше ли v значения А[х] или больше. Таким образом, на каждой итерации размер задачи уменьшается.
Анализ эффективности данного алгоритма показывает, что интерполяционный поиск в среднем требует менее сравнений ключей при поиске в списке из n случайных значений.