Задача поиска в таблице

В данном пособии основное внимание уделено задаче поиска данных в таблице по заданному значению ключа.

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

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

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

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

Некоторые представления таблиц показаны на рис. 1.1.

Рис. 1.1. Варианты представления таблиц: а – массив; б – бинарное дерево; в – массив списков

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

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

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

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

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

const

N = ...; {Размер таблицы (произвольная константа)}

type

KeyType = ...;

{Здесь может быть любой тип данных, допускающий

операции сравнения и присваивания; например,

Integer}

RecordType = KeyType;

{Как сказано выше, мы не будем отличать запись от ее

ключа}

TableType = array [1..N] of RecordType;

Поиск в массивах

Линейный поиск

Рассмотрим простейшую задачу поиска элемента в массиве.

Дан массив A, состоящий из n элементов, и дано значение x:

var

A: TableType; {Таблица (массив) данных}

x: KeyType; {Искомый элемент}

Требуется определить, содержится ли в массиве A элемент, равный x, и если содержится, то на каком месте (при каком значении индекса массива).

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

function LinearSearch(A: TableType, x: KeyType

): Integer;

var

i: Integer;

begin

i := 1;

while (i <= N) and (A[i] <> x) do

i := i+1;

if i <= N then LinearSearch := i {Успех}

else LinearSearch := 0; {Неудача}

end; {LinearSearch}

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

В программе намеренно не использован цикл for. Это сделано для более наглядного сравнения с алгоритмом, который будет описан ниже.

Оценим эффективность алгоритма линейного поиска. Очевидно, время его работы будет пропорционально числу элементов в массиве: T(n) = O(n). В таких случаях говорят, что алгоритм имеет линейную оценку относительно размера массива.

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

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

Можно добиться некоторого ускорения работы, оставаясь в рамках линейного поиска. Известен, например, полезный прием, который называется барьерным поиском. Для его использования необходимо, чтобы в конце (или в начале) массива оставалось одно свободное место. Поэтому предположим временно, что тип массива описан так:

var TableType1 = array [1..N+1] of RecordType;

При этом число записей по-прежнему равно n, а позиция n+1 не содержит данных. Тогда функция барьерного поиска будет выглядеть следующим образом:

function BarrierSearch(var A: TableType1, x: KeyType

): Integer;

var

i: Integer;

begin

i := 1;

A[N+1] := x; {Установка барьера}

while A[i] <> x do

i := i+1;

if i <= N then BarrierSearch := i {Успех}

else BarrierSearch := 0; {Неудача}

end; {BarrierSearch}

Отличие от предыдущего алгоритма заключается в том, что искомый элемент x искусственно добавляется в массив. В результате этого можно быть уверенным, что x будет найден в любом случае. Вопрос только в том, будет ли он найден среди n «настоящих» элементов массива или же встретится только в «искусственной» позиции n+1.

В чем выигрыш от использования барьера? Можно заметить, что это позволило упростить проверку в заголовке цикла. Поскольку же итерация цикла всего-то состояла из двух проверок и одного присваивания, отмена одной из проверок может уменьшить время выполнения процентов на 30. Это не меняет линейного характера оценки O(n), но не стоит пренебрегать существенным улучшением, которое достигается так просто. Однако напомним, что для применения барьера необходимо, чтобы с одного из концов массива была свободная позиция, причем доступная для записи.

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

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

Теперь предположим, что массив A является сортированным, т.е. значения в нем расположены по возрастанию значений ключа.

В этом случае можно применить совершенно иной, более быстрый алгоритм поиска, не требующий проверки всех подряд элементов. Вместо этого сравним искомый ключ x со значением среднего по порядку элемента массива, т.е. элемента с индексом (n+1)/2. Если n четное, то неважно, какой из двух средних элементов будет выбран.

Если x окажется меньше, чем проверяемый средний элемент, то ясно, что искомое значение может содержаться только в левой половине массива (или нигде). И наоборот, если x больше проверяемого элемента, то поиск надо продолжать в правой половине массива. В том и другом случае выполнение одной проверки позволяет в два раза уменьшить размер той части массива, в которой следует искать x. Далее та же процедура применяется к выбранной половине массива (т.е. проверяется элемент с индексом либо (n+1)/4, либо 3(n+1)/4) и т.д., пока не будет найден нужный элемент либо не обнаружится его отсутствие.

Описанный алгоритм называется бинарным поиском в массиве. Соответствующая функция поиска приведена ниже.

function BinarySearch(A: TableType, x: KeyType

): Integer;

var

i, j, q: Integer;

begin

i := 1; j := N;

repeat

q := (i + j) div 2;

if A[q] < x then

i := q + 1

else

j := q – 1;

until (A[q] = x) or (i > j);

if A[q] = x then BinarySearch := q {Успех}

else BinarySearch := 0; {Неудача}

end; {BinarySearch}

Переменные i и j играют роль подвижных границ той части массива, в которой может находиться значение искомого ключа. Каждое сравнение приводит к сужению вдвое интервала поиска за счет перемещения одной из этих границ.

Оценим эффективность алгоритма. Каждая итерация цикла (включающая проверку значения и смещение одной из границ) сокращает интервал поиска по меньшей мере в два раза. Поиск завершается, когда интервал сведется к одному элементу. Для этого придется выполнить не более log₂n итераций. Таким образом, можно сказать, что алгоритм бинарного поиска имеет логарифмическую оценку эффективности T(n) = O(log(n)).

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

Таблица 2.1

Если учесть, что одна итерация бинарного поиска заметно сложнее, чем одна итерация линейного поиска, то можно сделать примерно следующие выводы. Для очень маленьких таблиц, имеющих около 10 элементов, использование бинарного поиска не дает существенного выигрыша по сравнению с линейным. Для таблиц размером около 100 выигрыш уже ощутим, но необходимость использования бинарного поиска еще можно считать спорной (потому что на современных процессорах экономия составит не более нескольких микросекунд). Однако при размерах от 1000 и выше спорить уже не приходится, поскольку бинарный поиск работает просто несравнимо лучше, чем линейный.

Не будем только забывать, что для применимости бинарного поиска требуется, чтобы массив был сортированным.

Вопросы и упражнения

1. Как следует изменить алгоритм барьерного поиска, если свободная позиция находится не в конце, а в начале массива?

2. Есть такая математическая игра. Один человек задумывает число от 1 до 1 000, а другой должен определить это число, задав десять вопросов, на которые первый отвечает «Да» или «Нет». Какие вопросы следует задавать? Сколько потребуется вопросов, если задумано число от 1 до 1 000 000?

3. Дан массив целых чисел A = (–5, –2, 3, 8, 12, 12, 15, 20, 30, 35, 40, 41, 41, 49, 50). Выполните вручную алгоритм бинарного поиска для ключа x = 12 и для ключа x = 42, выписывая значения i, j, q, A[q].