приходится проводить несколько избыточных сравнений при успешном поиске (см. упр. 12).

Еще один вариант бинарного поиска, который осуществляется быстрее всех описанных при очень больших N, обсуждается в упр. 23. Но в упр. 24 вы найдете еще более быстрый метод...

*Поиск Фибоначчи. При рассмотрении многофазного слияния мы видели, что числа Фибоначчи могут играть такую же роль, что и степени числа 2. Подобное явление наблюдается и при поиске, где числа Фибоначчи позволяют разработать альтернативу бинарному поиску. Для некоторых компьютеров предлагаемый метод предпочтителен в связи с тем, что в нем используются только сложение и вычитание (без деления на 2). Следует различать процедуру, которую мы начинаем обсуждать, и важный численный метод, также называемый "поиском Фибоначчи", используемый для поиска максимума унимодальной функции [см. Fibonacci Quarterly 4 (1966), 265-269]. Совпадение названий* нередко приводит к недоразумениям!

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

На рис. 8 показано дерево Фибоначчи порядка 6. Оно больше похоже на реальный, не очень хорошо подстриженный куст, чем на другие деревья, которые мы рассматривали. Возможно, это связано с тем, что многие природные процессы описываются законом Фибоначчи. В целом, дерево Фибоначчи порядка к имеет Fk+i - 1 внутренних (на рисунке - круглых) и Fk+i внешних (на рисунке - квадратных) узлов. Строится оно следующим образом.

Если к = 0 или к = 1, дерево вырождается в [0

Если к >2, корнем является F; левое поддерево представляет собой дерево Фибоначчи порядка к - 1; правое поддерево представляет собой дерево Фибоначчи порядка к - 2 с числами, увеличенными на F.

Обратите внимание на то, что, за исключением внешних узлов, числа двух дочерних узлов каждого внутреннего узла отличаются от него на одну и ту же величину, и эта величина - не что иное, как число Фибоначчи (например, на рассматриваемом рисунке 5 = 8-Ft и И = 8-1-Ft). Если разница на каком-либо уровне составляет Fj, то на следующем уровне она будет равна Fj.i для левой ветви и Fj 2 - для правой. Так, например, 3 = 5 - F3, а 10 = 11 - F2.

Комбинируя эти наблюдения с механизмом распознавания внешних узлов, мы получим следующий алгоритм поиска.

Алгоритм F {Поиск Фибоначчи {Fibonaccian search)). Дана таблица записей R1R2 .. .Rn, ключи которых расположены в порядке возрастания Ki < К2 < < Kn-Алгоритм осуществляет поиск заданного аргумента К.

* Нужно отметить, что в английском языке такое совпадение превращается в обычную схожесть; метод поиска, который мы будем рассматривать, именуется "Fibonaccian search" а метод поиска максимума унимодальной функции - "Fibonacci search". - Прим. перев.

Рис. 8. Дерево Фибоначчи порядка 6.

Для удобства описания предполагается, что Л -I- 1 представляет собой число Фибоначчи Fk+i (выполнив соответствующую инициализацию, алгоритм несложно распространить на любые значения TV; см, упр. 14).

F1. [Инициализация.] Установить г <- Fk, р <- ffc-i, q <r- Fk-2- (В описании этого алгоритма pviq означают последовательные числа Фибоначчи.)

F2. [Сравнение.] Если К < Ki, перейти к шагу F3; если К > Ki, перейти к шагу F4; если К - Ki, алгоритм успешно завершается.

F3. [Уменьшение г.] Если g = О, алгоритм завершается неудачно. В противном случае следует установить г г - g и (р, д) [q, p-q); затем перейти к шагу F2.

F4. [Увеличение г.] Если р = 1, алгоритм завершается неудачно. В противном случае следует сначала установить i+-i + q, p+-p-q, а. затем - g ч- g - р и перейти к шагу F2.

В приведенной ниже MIX-реализации алгоритма используется дублирование внутреннего цикла для повышения скорости работы. В одном из циклов р хранится в г12, а q - в г13; в другом цикле регистры меняются ролями. В действительности в регистрах хранятся значения р - 1 и g - 1, что облегчает проверку "р =1?" на шаге F4.

Программа F [Поиск Фибоначчи). Мы придерживаемся предварительных соглашений; гА = К, гИ = г, (г12 или г13) = р - 1, (г13 или г12) = q-l.

01 START LDA К 1 Fl. Инициализация.

02 ENTl Fk 1 i<r-Fk.

03 ENT2 Fk-i-1 1 pFk-i.

04 ENT3 Pfc-2-1 1 q<r-Fk-2.

05 JMP F2A 1 Переход к шагу F2.

06 F4A INCl 1,3 C2-5-A F4. Увеличение i. i<~i + <].

07 DEC2 1,3 C2-5-A p<r-p-q.

08 DEC3 1,2 C2-5-A qq-p.

09 F2A CMPA KEY.l С F2. Сравнение.

10 JL F3A С Переход к шагу F3, если К < Ki.

11 JE SUCCESS С2 Выход, если К = К.

Время работы этой программы анализируется в упр. 18. Из рис. 8 видно (и анализ это доказывает), что левая ветвь выбирается чаще, чем правая. Обозначив количество выполнения шагов F2, F3 и F4 через С, С1 и (С2 - 5) соответственно, получим

C=(ave фк/у/5 + 0{1), max к-1),

С1 = (ave k/V5 + 0{l), max к - 1), (8)

С2-S = {ауеф-к/л/5 + 0{1), max [A:/2J).

Таким образом, левая ветвь выбирается примерно в ф 1.618 раз чаще, чем правая (вполне понятный и предсказуемый результат, поскольку после каждого сравнения оставшийся интервал делится на две части; левая часть при этом приблизительно в ф раз больше правой). В итоге суммарное среднее время работы программы F составляет около

i((18 + 4ф)к + 31 - 26ф)и « (7.050IgiV + 1.08)u

для успешного поиска плюс {9 - Зф)и ss 4.15u - для неудачного. Это меньше, чем в случае использования программы С, хотя наихудшее время работы (около 8.6 Ig Л) несколько больше.

Интерполяционный поиск. Забудем ненадолго о компьютерах и посмотрим, как с задачей поиска справляется человек. Очень часто хороший алгоритм можно создать, проанализировав собственные действия в реальной жизни.

Представьте, что вы ищете слово в словаре. Вероятно, вы не станете открывать словарь посередине и идти к странице, расположенной на 1/4 или 3/4 от начала, т. е. выполнять алгоритм бинарного поиска. Шансы на то, что вы воспользуетесь поиском Фибоначчи, просто смехотворны. Но ведь вы находите нужное слово в словаре? Так как же вы это делаете?

Если слово начинается с буквы А, вероятно, вы ищете его в начале книги. Во многих словарях есть ярлычки, которые позволяют мгновенно найти страницу, на которой начинаются слова на заданную букву. Данная технология ускорения