Рашмор-оптимизация в Microsoft Visual FoxPro

Пусть упорядоченный массив x(1:n) содержит, например, элементы 5, 7, 11, 18, 26, 32, 44, 57, 81, 90, 94, 97, 107, 116, 129, 147, 179 и пусть задан аргумент поиска key, равный, например, 129.

Идея алгоритма бинарного поиска такова:

- сравнить аргумент поиска key со значением среднего элемента x(mid) массива x, где mid = [n/2], а [c] – целая часть числа c;

- если они равны, то поиск завершен, иначе, если key < x(mid), выполнить аналогичным образом поиск в позициях массива x, предшествующих позиции mid, в противном случае, если key ≥ x(mid), выполнить аналогичным образом поиск в позициях массива x, следующих за позицией mid.

Исключить из дальнейшего рассмотрения часть массива позволяет тот факт, что массив упорядочен.

Проиллюстрируем процесс бинарного поиска. Число элементов массива n = 17, тогда [n/2] = 8. Поэтому первоначально выполняется сравнение key с x₈ = 57. Так как key > x₈, то зона поиска на следующем шаге ограничивается участком от 9-го элемента до 17-го. Этот участок состоит из девяти элементов и его серединой является элемент x₁₃ = 107 ([(9 + 17)/2] = 13). Поскольку key > x₁₃, то зона поиска ограничивается участком от 14-го до 17-го элемента. Его серединой является элемент x₁₅. На этом процесс поиска завершен, так как x₁₅ = key. Всего для завершения поиска потребовалось 3 итерации.

Отобразим на рис. 8.1 процесс поиска элемента key = 129, выделяя посредством подчеркивания на каждом шаге зоны поиска.

Рис. 8.1. Пример дихотомии

Каждое сравнение уменьшает число возможных кандидатов в два раза. Максимальное число шагов поиска будет в том случае, когда искомый элемент находится в начале или в конце массива. Для завершения поиска потребуется не более log₂n + 1 итераций. Действительно, если число элементов в массиве равно n = 2^m, то элемент будет найден через m шагов. В свою очередь, при заданном n имеем m = log₂n. После анализа последнего элемента получаем общее число итераций log₂n + 1. Поэтому вычислительная сложность бинарного поиска составляет O(log₂n). Вычислительная сложность последовательного поиска равна O(n).

Однако приведенный алгоритм не позволяет в общем случае точно решить задачу поиска, когда файл или массив содержат повторяющиеся значения ключей. Рассмотрим, например, массив 5 7 11 18 26 32 44 57 81 90 94 97 107 129 129 147 179, в котором элемент (ключ) 129 содержится два раза. Тогда, если аргумент поиска равен 129, поиск по приведенному алгоритму завершится на элементе с номером 15, то есть будет найдено не первое, а второе значение ключа 129 (первое значение ключа расположено в позиции 14). В ряде случаев эта неточность принципиальна, впрочем, она легко устраняется.