Pi P2 Pff

Рис. 2. Расположение в виде "органных труб" минимизирует среднее время сцепленного поиска.

a + b{Li+i +----\-Lj) к d(j,i) =a + b(Lj+i +----\-Ln) + г+ b{Li-\-----\-Li), где г - время

перемотки.)

20. [М28] Продолжая выполнять упр. 18, найдите оптимальное расположение для сцепленного поиска в случае, когда d{i,j) = min{dij,d„-\i-j\) и dx < d2 < (Эта ситуация встречается, например, в двусвязном циклическом списке или в запоминающем устройстве с возможностью перемещения в обе стороны.)

21. [М28] Рассмотрим п-мерный куб с координатами вершин (di,..., dn), где dj = О или 1; две вершины называются соседними, если они различаются только одной координатой. Предположим, что набор из 2" чисел Хо < Хх < < Х2-х должен быть сопоставлен 2" вершинам таким образом, чтобы минимизировать сумму \xi - Xj\; сумма берется

по всем i и j, таким, что Xi и Xj сопоставлены соседним вершинам. Докажите, что этот минимум достигается тогда, когда для Bcexj xj сопоставлено вершине, координаты которой являются двоичным представлением числа j.

► 22. [20] Предположим, что в большом файле ва.м необходимо найти 1 ООО ближайших к данному ключу записей, т. е. записей, для которых функция расстояния d{Kj,K) принимает наименьшие значения. Какая структура данных будет самой подходящей для такого последовательного поиска?

Пытайся до конца, сомнений прочь оскал, И, все преодолев, найдешь ты, что искал*.

- РОБЕРТ ХЕРРИК (ROBERT HERRICK), Ищите и обрящете (Seeke and finde) (1648)

Перевод Светланы Тригуб.

6.2. ПОИСК ПУТЕМ СРАВНЕНИЯ КЛЮЧЕЙ

В этом РАЗДЕЛЕ МЫ обсудим методы поиска, основанные на линейном упорядочении ключей (таком, как числовое или алфавитное). После сравнения данного аргумента К с ключом Ki из таблицы поиск продолжается одним из трех путей, в зависимости от того, какое из условий - К < Ki, К = Ki или К > Ki - истинно. Последовательные методы поиска, рассмотренные в разделе 6.1, по сути, имели только два варианта ветвления поиска - в зависимости от выполнения или не выполнения условия К = Ki; при отказе от исключительно последовательного доступа к таблице можно организовать более эффективный поиск с использованием отношения порядка.

6.2.1. Поиск в упорядоченной таблице

Что вы станете делать, если вам вручат большой телефонный справочник и попросят найти владельца телефона 444-3522? Вряд ли вы сможете предложить что-то лучшее, чем метод последовательного поиска из раздела 6.1 (методы наподобие "позвонить и спросить, кто это" и "купить компакт-диск с телефонной базой данных службы 09" не рассматриваются). Беда в том, что, хотя в справочнике и содержится вся необходимая информация для поиска как по имени абонента, так и по его номеру, поиск по имени владельца гораздо проще именно благодаря упорядочению записей в телефонном справочнике. Последовательный поиск в огромном файле - это почти всегда безумие и пустая трата времени, но если файл упорядочен, решить задачу намного проще.

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

Ki < К2 < < Kn

и в которой мы имеем простой и быстрый доступ к ключу в любой заданной позиции. После сравнения в такой таблице К я Ki мы получим один из трех результатов:

• К <К,

• к = к,

• кж,

[Ri,Ri+iRn исключаются из рассмотрения]; [поиск завершен];

[Ri,R2,-..,Ri исключаются из рассмотрения].

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

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

BI. Иницигшизация

В2. Получение средины

В4. Изменение и

и<1

-> Неудачное завершение

В5. Изменение /

(ВЗ. Сравнение

Успешное завершение

Рис. 3. Бинарный поиск.

применить ту же процедуру к половине таблицы. Максимум за величину порядка IgiV сравнений мы найдем искомый ключ (либо установим, что его нет в таблице). Эта процедура известна как "логарифмический поиск" или "метод деления пополам" но чаще всего употребляется термин бинарный поиск.

Хотя основная идея бинарного поиска сравнительно проста, детали его реализации нетривиальны и много неплохих программистов ошибались при первых попытках написать соответствующую программу. В одной из наиболее популярных форм реализации метода используются два указателя, I и и, которые указывают верхнюю и нижнюю границы поиска.

Алгоритм В {Бинарный поиск (Binary search)). Дана таблица записей R1R2 .. Rn, ключи которых расположены в порядке возрастания: К, < К2 < < К; алгоритм используется для поиска в таблице заданного аргумента К.

81. [Инициализация.] Установить Z 1, и TV.

82. [Получение средины.] (На этом шаге мы знаем, что если К имеется в таблице, то справедливо условие Ki < К < К и- Более точное описание ситуации можно найти в приведенном ниже упр. 1.) Если и <1, алгоритм завершается неудачно; в противном случае следует установить г {1 + и)/2 , чтобы i соответствовало примерно средине рассматриваемой части таблицы.

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

84. [Изменение и.] Установить и <г- i - 1 и перейти к шагу В2.

85. [Изменение /.] Установить Z г -Ь 1 и перейти к шагу В2.

На рис. 3 приведена блок-схема алгоритма, а на рис. 4 показаны два случая проведения бинарного поиска: в первом разыскивается число 653, имеющееся в таблице, а во втором - число 400, отсутствующее в таблице. Скобки показывают положение указателей I я и, а подчеркнутое число - Ki- В обоих случаях поиск завершается после вьшолнения четырех сравнений.