Постановка задачи

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

Пусть К есть некоторый массив из N ключей, а X - некоторый набор записей, такой, что K(I) является ключом записи X(I). Пусть А является некоторым аргументом поиска.

Алгоритмом поиска называется определенный алгоритм, который воспринимает некоторый аргумент А и исследует последовательность записей xL, xL+1,..., xp с тем, чтобы найти некоторую запись, ключ которой равен А.

Целью поиска является информация, содержащаяся в записи, ассоциированной с данным ключом. Интервал от L до P называется интервалом поиска.

При реализации алгоритма поиска существуют две возможности его

окончания:

1) либо поиск оказался удачным, т.е. позволил определить положение соответствующей записи, содержащей ключ А,

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

Различают методы поиска:

1) внешние и внутренние, статические и динамические, где статический

означает, что содержимое набора данных остается неизменным, а динами-

ческий означает, что набор является объектом частых вставок и удалений;

2) основанные на сравнении ключей и цифровых свойствах ключей;

3) использующие истинные ключи и работающие с преобразованными ключами.

Мы будем изучать внутренние, статические методы поиска, основанные

на просмотре записей и на сравнении их ключей.