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

(ISlgA - 16)и для успешного поиска,

(ISlgA + 12) U для неудачного поиска

(в предположении равновероятных исходов поиска).

Важное изменение. Вместо трех указателей (/, г и и) в процессе поиска можно использовать только два: текущее положение г и величину его изменения <5. После каждого сравнения, не давшего равенства, мы можем установить i <- i±S и S <- S/2 (приблизительно). Это вполне возможный путь, хотя и требующий исключительного внимания к мельчайшим деталям, как в приведенном ниже алгоритме. Более простые подходы будут неработоспособны.

Алгоритм и (Однородный бинарный поиск (Uniform binary search)). Дана таблица записей Ri,R2,.. ,Rn, ключи которых расположены в порядке возрастания: Кг < К2 < < Kn- Алгоритм обеспечивает поиск заданного аргумента К. В случае четного N алгоритм будет обращаться к фиктивному ключу Ко, значение которого должно быть равно -оо (или любому значению, меньшему К). Алгоритм работает в предположении, что Л > 1.

U1. [Инициализация.] Установить г [Л/2], т \NI2\.

U2. [Сравнение.] Если К < Ki, перейти к шагу U3; если К > Ki, перейти к шагу U4; если К = Ki, алгоритм успешно завершен.

из. [Уменьшить г.] (Мы определили интервал продолжения поиска, содержащий т или т-1 записей; г указывает на первый элемент справа от интервала.) При m = О алгоритм завершается неудачно. В противном случае следует сначала установить i <- i - \т/2], а затем - т <- [m/2j и перейти к шагу U2.

U4. [Увеличение г.] (Мы определили интервал продолжения поиска, содержащий т или т-1 записей; i указывает на первый элемент слева от интервала.) При m = О алгоритм завершается неудачно. В противном случае следует сначала установить г +-г + Гт/2], а затем - m ч- [m/2j и перейти к шагу U2.

На рис. 6 показано бинарное дерево, соответствующее поиску при Л = 10. В случае неудачного поиска алгоритм может выполнить излишнее сравнение непосредственно перед окончанием работы; такие узлы на рисунке заштрихованы. Мы называем этот процесс поиска однородным потому, что разность между числами узла на уровне / и его узла-предшественника на уровне 1 - 1 представляет собой константу S для всех узлов на уровне I.

Теория, лежащая в основе алгоритма U, может быть пояснена следующим образом. Предположим, что у нас имеется интервал для поиска длиной п-1; сравнение со средним элементом (для четного п) или с одним из средних элементов (для нечетного п) дает нам два интервала - длиной [n/2J - 1 и Гп/2] - 1. После повторения этого процесса к раз мы получим 2* интервалов, наименьший из которых имеет длину [n/2*J - 1, а наибольший - Гп/2*] - 1. Следовательно, длина двух интервалов на одном уровне отличается не более чем на единицу; это делает возможным выбор "среднего" элемента без запоминания точных значений длин интервалов.

.5 = 3 <5=1 <5=1

Рис. 6. Дерево сравнений для "однородного" бинарного поиска при Л = 10.

Принципиальное достоинство алгоритма U заключается в том, что нам совершенно не нужно хранить значение тп; необходима только ссылка на небольшую таблицу S для использования на каждом уровне дерева. Таким образом, алгоритм сводится к следующей процедуре, одинаково подходящей как для бинарных, так и для десятичных компьютеров.

Алгоритм С {Однородный бинарный поиск). Этот алгоритм подобен алгоритму U, но использует вспомогательную таблицу вместо вычислений:

DELTA ЕЯ = для 1 < j < [Ig 7VJ + 2. (6)

Cl. [Инициализация.] Установить i <- DELTA[1], j 2.

C2. [Сравнение.] Если К < Ki, перейти к шагу СЗ; если К > Ki, перейти к шагу С4; если К = Ki, алгоритм успешно завершается.

СЗ. [Уменьшение г.] Если DELTA [j] = О, алгоритм завершается неудачно. В противном случае установить i +- i - DELTA [j], j j -f 1 и перейти к шагу С2.

С4. [Увеличение г.] Если DELTA [j] = О, алгоритм завершается неудачно. В противном случае установить г г -I- DELTA [j], j j + \ и перейти к шагу С2.

В упр. 8 доказывается, что настоящий алгоритм использует искусственный ключ Ко = -оо только при четных N.

Программа С {Однородный бинарный поиск). Эта программа выполняет ту же задачу, что и программа В, используя алгоритм С; при этом гА = К, гП = г, г12 = j, г13 = DELTA [j].

Cl. Инициализация, i <- [(Л 4- 1)/2J. J<-2.

01 START

02 OS 04

05 3H

06 07

08 5H

ENTl N+1/2 ENT2 2 LDA К JMP 2F JE SUCCESS J3Z FAILURE DECl 0,3 INC2 1

1 1 1 1

Cl Cl-5

Переход, если К = Ki. Переход, если DELTA [ji = 0. Cl-5-A C3. Уменьшение i. С - 1 J <- j + 1.

Рис. 7. Дерево сравнений для почти равномерного поиска по методу Шара при Л = 10.

В случае успешного завершения поиска данный алгоритм соответствует бинарному дереву с такой же длиной внутреннего пути, как и в алгоритме В, поэтому среднее количество сравнений Cn остается прежним. При неудачном поиске алгоритм С всегда выполняет в точности [IgAJ -f 1 сравнений. Общее время работы программы С не совсем симметрично по отношению к левым и правым ветвям, и С1 имеет больший вес, чем С2. Впрочем, в упр. 11 будет показано, что случаи К < Kt имеют ту же вероятность, что и К > Ki. Следовательно, программа С работает приблизительно следующее время:

(8.51giV-6)u (8.5[lg7VJ + 12)w

при успешном поиске, при неудачном поиске.

Это более чем в два раза быстрее программы В; при этом специфика бинарного компьютера не используется (в случае времени работы (5) программы В предполагалось наличие команды битового сдвига в компьютере MIX).

Другая модификация бинарного поиска, предложенная в 1971 году Л. Э. Шаром (L. Е. Shar), на некоторых компьютерах будет работать еще быстрее, так как она однородна после первого шага и не требует использования таблицы. Первый шаг состоит в сравнении К п Ki, где г = 2*, /с = [IgiVJ. Если К < Ki, мы используем однородный поиск с 6 = 2*~\ 2*", ...,1,0. С другой стороны, если К > Ki, мы

и, делая вид, что первое

устанавливаем г = г = Л -I-1 - 2, где I = [lg(A -2*-1-1) сравнение на самом деле было К > Кг-, используем бинарный поиск с <5 = 2~\ 2~, ...,1,0.

Метод Шара для iV = 10 проиллюстрирован на рис. 7. Подобно предыдущим алгоритмам, он никогда не выполняет больше [IgAJ -f 1 сравнений. Следовательно, выполняемое им количество сравнений превышает минимально возможное среднее значение не более чем на единицу - несмотря на то, что иногда алгоритму