поиска вполне применима в мире компьютеров; о таких алгоритмах мы поговорим в разделе 6.3.

Но и после этого первого шага ваши действия ничуть не похожи на то, что происходит при реализации какого-либо из рассмотренных алгоритмов. Если вы заметите, что искомое слово находится ближе к концу группы слов на нужную букву, вы просто пропустите изрядное количество страниц (или начнете поиск от следующей буквы к предыдущей). Вот в чем состоит основное отличие ваших действий от действий, выполняемых в алгоритмах, для которых понятия "немного больше" и "существенно больше" одинаковы.

Эти рассуждения приводят нас к алгоритму, который может быть назван интерполяционным поиском: если мы знаем, что К находится между Kt и К, следующую проверку мы будем делать примерно на расстоянии (К - Kt)/{Ku - Kt) от / (в предположении, что ключи представляют собой числовые значения, близкие к арифметической прогрессии).

Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный поиск. В то время как один шаг бинарного поиска уменьшает количество проверяемых записей от п до п, один шаг интерполяционного поиска уменьшает это количество до у/п (если ключи распределены в таблице случайным образом). В результате интерполяционный поиск требует в среднем IglgA шагов для уменьшения диапазона проверки от iV до 2 (см. упр. 22).

Однако имитационные вычислительные эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (пока таблица не очень велика). Кроме того, типичные таблицы недостаточно случайны, да и разница между значениями IglgA и IgN становится значительной только при больших N (скажем, при N 2 = 65 536).

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

История и библиография. Наиболее ранним известным примером рассортированного для упрощения поиска длинного списка элементов является известная вавилонская таблица обратных величин Инакибит-Ану, датируемая примерно 200 г. до н. э. Эта глиняная табличка содержит более 100 пар значений, которые представляют собой начало списка из приблизительно 500 многозначных шестидесятеричных чисел и их обратных величин, рассортированных в лексикографическом порядке. Например, список включает последовательность

01 13 09 34 29 08 08 53 20 49 12 27

01 13 14 31 52 30 49 09 07 12

01 13 43 40 48 48 49 41 15

01 13 48 40 30 48 46 22 59 25 25 55 33 20

01 14 04 26 40 48 36

Сортировка 500 подобных чисел при помощи технологий тех времен является просто феноменальной! [См. D. Е. Knuth, Selected Papers on Computer Science (Cambridge Univ. Press, 1996), Chapter 11.]

Представляется совершенно естественной сортировка числовых значений, однако отношение порядка для букв или слов не столь очевидно. Тем не менее уже в наиболее древних алфавитах имелись последовательности букв, которые служили для их сравнения. Например, во многих библейских псалмах содержатся стихи, следующие друг за другом в строгом алфавитном порядке: первый стих начинается с альфы, второй - с беты и т. д., что облегчает запоминание. Часто стандартная последовательность букв использовалась семитами и греками для обозначения чисел*, например а, и 7 означали 1, 2 и 3 соответственно.

Алфавитный порядок слов, который представляется сейчас естественным даже школьнику, был гораздо более поздним изобретением и потребовал немалой работы. Отдельные списки, датируемые примерно 300 г. до н. э., которые были найдены на островах Эгейского моря, содержат имена членов некоторых религиозных общин, упорядоченные только по первой букве (представляя, таким образом, результат одного прохода поразрядной сортировки слева направо). Некоторые греческие папирусы, датируемые 134-135 г. н. э., содержат списки налогоплательщиков, упорядоченных по первым двум буквам. Аполлоний Софист** (Apollonius Sophista) использовал алфавитный порядок по первым двум буквам (а иногда и по последующим) в своем словаре поэзии Гомера (1 в. н. э.). Известны примеры более совершенного упорядочения, например Hippocratic Glosses Галена*** (ок. 200 г.), но это было крайне редким явлением. По первым буквам были упорядочены слова и в Etymologiarum Св. Исидора (St. Isidorus)**** (ок. 630 г., книга X), а в Corpus Glossary (ок. 725 г.) использоваяись только две первые буквы каждого слова. Эти две работы были, пожалуй, крупнейшими нечисловыми файлами данных, скомпилированными в средние века.

Впервые описание алфавитного порядка появилось в Catholicon Джованни Генуэзского (Giovanni di Genoas) в 1286 году. В предисловии поясняется, что

ато предшествует ЫЬо

аЬео предшествует adeo

amatus предшествует amor

imprudens предшествует impudens

iusticia предшествует iustus

polisintheton предшествует polissenus

(т. е. приводятся примеры ситуаций, в которых порядок следования слов определяется первой, второй, ..., шестой буквами) "и далее точно так же! Он отмечает, что для изобретения подобного способа упорядочения слов потребовались значительные усилия. "Я прошу тебя, читатель, не презирать мой огромный труд и этот порядок, как нечто ничего не стоящее."

Подробным изучением развития алфавитного порядка до начала книгопечатания занимался Ллойд В. Дейли (Lloyd W. Daly) [Coiiection Latomus 90 (1967), 100 р.].

* Такгья же система была принята в Древней Руси: применялись алфавит и специальный символ ("титло"), а также некоторые дополнительные обозначения для тысяч, миллионов и т. д. - Прим. перев.

** Один из грамматиков древности; выходец из Александрии. *** Римский врач и естествоиспытатель, классик античной медицины. **** Исидор Севильский - испанский епископ, выдающийся ученый и писатель.

Им найдено несколько интереснейших старинных рукописей, которые, несомненно, использовались в качестве черновых записей при сортировке слов по первой букве (см. с. 89-90 его монографии).

В первом словаре английского языка Роберта Коудри (Robert Cawdrey) Tabie Alphabetical! (London, 1604) содержатся следующие инструкции.

Если слово, которое ты ищешь, начинается с "а", то ищи его в начале, а если оно

начинается с "v" то ищи его в конце книги. Опять-таки, если слово начинается с

"са", то искать его следует в начале буквы "с", а если с "си", то смотреть надлежит

в конце этой буквы. И так поступай до конца слова. Создается впечатление, что Коудри сам учился своему методу расставления слов в алфавитном порядке в процессе работы - на первых страницах словаря многие слова находятся не на своих местах, в то время как остальная часть словаря содержит гораздо меньше ошибок.

Бинарный поиск был впервые упомянут Джоном Мочли (John Mauchly) в, пожалуй, первой опубликованной дискуссии о нечисленных методах программирования [Theory and Techniques for the Design of Electronic Digital Computers, edited by G. W. Patterson, 1 (1946), 9.7-9.8; 3 (1946), 22.8-22.9]. Метод становится хорошо известным программистам, однако ни у кого не возник вопрос, как работать с Л, не равным 2" - 1. [См. А. D. Booth, JVature 176 (1955), 565; А. L Dumey, Computers and Automation 5 (December, 1956), 7 (здесь бинарный поиск назван так: "Двадцать вопросов"); Daniel D. МсСгаскеп, Digital Computer Programming (Wiley, 1957), 201-203; М. Halpern, CACM 1,1 (February, 1958), 1-3.]

Д. Г. Лехмер (D. H. Lehmer), пожалуй, был первым, кто опубликовал алгоритм бинарного поиска, работающий при любых Л [Ргос. Symp. Appl. Math. 10 (1960), 180-181]. Следующий шаг был сделан Г. Боттенбруком (Н. Bottenbruch), который представил интересный вариант алгоритма В, в котором отдельные проверки равенства отодвигаются в конец алгоритма [JACM 9 (1962), 214]. Используя г <- [(1+и)/2] вместо г <- [{I + и)/2\ на шаге В2, он устанавливает I <- i при К > Ki; тогда и - I уменьшается на каждом шаге. В конце, когда I = и, мы имеем Ki < К < Ki+i и можем проверить, является ли поиск успешным, при помощи еще одного сравнения (Боттенбрук полагал, что изначально К > Ki). Данная идея позволяет несколько ускорить внутренний цикл на многих компьютерах; этот же принцип может быть применен и к другим алгоритмам поиска, обсуждавшимся в этом разделе. Впрочем, успешный поиск потребует в среднем около одной дополнительной итерации в соответствии с (2). Так как внутренний цикл вьшолняется примерно около IgN раз, более быстрый цикл сможет компенсировать дополнительную итерацию только при очень больших Л (см. упр. 23).

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

К. Ю. Айверсон (К. Е. Iverson) [А Programming Language (Wiley, 1962), 141] привел описание алгоритма В, однако не рассмотрел случай неудачного поиска. Д. Э. Кнут (D. Е. Knuth) [САСМ 6 (1963), 556-558] представил алгоритм В в качестве примера, использованного автоматической системой построения блок-схем. Однородный бинарный поиск (алгоритм С) бьш предложен автору А. К. Чандрой (А. К. Chandra) из Станфордского университета в 1971 году.