t> 12.29 Укажите порядок ключей после того, как элементы с ключами Е А S Y Q U Е S Т I О N помещаются в первоначально пустую таблицу, когда после выполнения операции search вызывается insert по причине отсутствия элемента, причем применяется эвристический самоорганизующийся поиск с перемещением вперед (см. упражнение 12.28).

12.30 Создайте программу-драйвер для методов самоорганизующегося происка, в которой функция insert используется для заполнения таблицы символов Л ключами, а затем выполняется 107V поисков для обнаружения элементов в соответствие с заранее определенным распределением вероятностей.

12.31 Воспользуйтесь рещением упражнения 12.30 для сравнения времени выполнения реализации из упражнения 12.20 и времени выполнения реализации из упражнения 12.28 для Л= 10, 100 и 1000, используя распределение вероятностей, при котором вероятность успешного выполнения операции search для /-го наибольшего ключа равна 1 / 2 при 1 < / < 7V.

12.32 Выполните упражнение 12.31 для распределения вероятностей, при котором вероятность успешного выполнения операции search для /-го наибольшего ключа определяется соотношением Я/ / при \ < i < N. Это распределение называется законом Зипфа.

12.33 Сравните эвристическое перемещение вперед с оптимальной организацией для распределений, указанных в упражнениях 12.31 и 12.32, поддерживающей размещение ключей в порядке возрастания (в порядке уменьшения ожидаемой частоты обращения к ним). То есть, в упражнении 12.31 вместо решения из упражнения 12.20 воспользуйтесь программой 12.5.

12.4 Бинарный поиск

в реализации последовательного поиска на базе массивов общее время поиска на больших наборах элементов можно значительно уменьшить, используя процедуру поиска, основанную на стандартном подходе разделяй и властвуй (см. раздел 5.2). Для этого набор элементов необходимо разделить на две части, определить, к какой из двух частей принадлежит ключ поиска, а затем сосредоточить свои усилия именно на этой части. Рациональный способ разделения наборов элементов на части состоит в поддержке элементов в отсортированном виде с последующим использованием индексов в отсортированном массиве для определения части массива, над которой будет выполняться дальнейшая работа. Такая технология поиска называется бинарным поиском. Программа 12.7 представляет рекурсивную реализацию этой основополагающей стратегии. В программе 2.2 показана нерекурсивная реализация метода, при которой никаких стеков не требуется.

А А А с Е Е Е©Н I L М N Р R Н 1 L (М) N Р R H©L

РИСУНОК 12.1 БИНАРНЫЙ ПОИСК

При бинарном поиске для нахождения искомого ключа L в этом примере файла используются только три итерации. В первом вызове алгоритм сравнивает L с ключом в середине файла - G. Поскольку L больше этого ключа, в ходе следующей итерации исследуется правая половина файла. Затем, поскольку L меньше М, находящегося в середине правой половины, в ходе третьей итерации исследуется подфайл, состоящий из трех элементов, в который входят ключи Н, I и L. После выполнения еще одной итерации размер подфайла становится равным 1 и алгоритм находит ключ L.

РИСУНОК 12.2 БИНАРНЫЙ ПОИСК

При бинарном поиске требуется только семь итераций для нахождения записи в файле, который состоит из 200 элементов. Размеры подфайлов описываются последовательностью 200, 99, 49, 24, 11, 5, 2, 1; несложно заметить, что каждая из исследуемых частей несколько меньше предыдущей.

поскольку рекурсивная функция в программе 12.7 завершается рекурсивным вызовом.

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

Лемма 12.5 При бинарном поиске никогда не используется более чем сравне-

ний (для выявления попадания или промаха).

См. лемму 2.3. Интересно отметить, что максимальное количество сравнений, используемых для бинарного поиска в таблице, размер которой равен n, в точности равен количеству бит в двоичном представлении числа n, поскольку операция сдвига одного бита вправо преобразует двоичное представление n в двоичное представление числа In/ 2j (см. рис. 2.6).

Поддержка таблицы в отсортированном виде, как это делается при сортировке вставками, приводит к тому, что время выполнения становится квадратичной функцией от количества операций insert, но эта стоимость может оказаться приемлемой или ею даже можно пренебречь, если количество операций search очень велико. В типичной ситуации, когда все элементы (или большая их часть) доступны до начала поиска, можно построить (construct) таблицу символов с помошью конструктора, который принимает массив в качестве аргумента и использует один из стандартных методов сортировки, описанных в главе 6 и последуюших главах, для сортировки таблицы во время инициализации. После этого обновление таблицы может выполняться различными способами. Например, можно поддерживать порядок во время вставки, как это делается в программе 12.5 (см. также упражнение 12.21), либо объединить вставляемые элементы в пакет, выполнить сортировку и объединить с сушествуюшей таблицей (как описано в упражнении 8.1). Всякое обновление может быть связано со вставкой элемента, ключ которого меньше ключа какого-либо из элементов таблицы, поэтому может потребоваться перемешение любого элемента с целью освобождения места. Упомянутая вероятность высокой стоимости обновления таблицы - наибольший недостаток использования бинарного поиска. С другой стороны, существует ог-

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

Если новые элементы требуется вставлять динамически, может показаться, что для этого нужна связная структура. Однако сам по себе связный список не позволяет создавать эффективную реализацию, поскольку эффективность бинарного поиска зависит от возможности быстро попасть в середину любого подмассива через индексирование, а единственный способ попасть в середину связного списка - это отслеживание ссылок. Для суммирования эффективности бинарного поиска и гибкости связных структур требуются более сложные структуры данных, которые мы начнем исследовать вскоре.

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

Программа 12.7 Бинарный поиск (в таблице символов, основанной на массиве)

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

Массив должен быть отсортированным. Эта функция может рассматриваться в качестве замены функции search из программы 12.5, которая обеспечивает динамическую сортировку во время вставки. Можно было бы также добавить конструктор таблицы символов, который получал бы массив в качестве аргумента, а затем строил бы таблицу символов на основе элементов входного массива и сортировал бы ее для целей поиска с применением одной из стандартных процедур сортировки.

private:

Item searchR(int 1, int г, Key v) { if (1 > r) return nullltem; int m = (l+r)/2;

if (v == st[m].key()) return st[m]; if (1 == r) return nullltem; if (V < st[m] -key 0 )

return searchR(l, m-1, v) ; else return searchR(m+l, r, v);

public: Item search (Key V)

{ return searchR(0, N-1, v); }