Линейный (последовательный) поиск

Поиск

10.1 Поиск: определение и общая терминология

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

Дадим определение. Поиск (searching, retrieval) - это алгоритм, который воспринимает некоторый аргумент ArgSearch и пытается локализовать (найти, определить) запись, ключ которой равен ArgSearch. Значение ArgSearch называется аргументом поиска.

Алгоритм поиска может возвратить всю найденную запись или чаще всего может возвратить некоторый указатель на эту запись. Поиск, по завершении которого найдена запись с ключом, равным аргументу поиска, называется успешным или результативным. Успешный поиск часто завершаетсяизвлечением. Однако возможно, что поиск некоторого конкретного аргумента в таблице является неудачным (безрезультатным), т. е. в данной таблице не существует записи с этим аргументом в качестве ключа. В этом случае такой алгоритм может возвратить некоторую специальную «пустую запись» или некоторый пустой указатель. Однако чаще такое условие приводит к появлению некоторой ошибки или к установке во флаге некоторого конкретного значения, которое указывает, что искомая запись отсутствует. Если поиск закончился неудачно, то часто бывает желательно добавить некоторую новую запись с аргументом ArgSearch в качестве ключа. Алгоритм, который выполняет эту функцию, называетсяалгоритмомпоискаивставки.

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

Как указывалось ранее, таблица может быть физически организована по-разному. Это может быть массив записей, связанный список, дерево или даже граф. Поскольку различные методы поиска могут соответствовать различным организациям таблиц, то таблица часто строится, исходя из соображений конкретного метода поиска. Такая таблица может полностью располагаться в оперативной памяти, или во вспомогательной памяти, или там и там. Ясно, что для разных организаций таблиц необходимы различные методы поиска. Методы поиска, при которых вся таблица постоянно находится в оперативной памяти, называются методамивнутреннегопоиска, а те методы, для которых большая часть таблицы хранится во вспомогательной памяти (такой, как диск или лента), называются методами внешнегопоиска. Мы будем рассматривать только внутренний поиск.

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

В языке Pascal имеется тип, подходящий для описания типа элементов таблицы, – это тип Record (запись), следовательно, тип элемента таблицы может быть задан, например, как

Type

Key: Word;

{описания других полей}

end;

где Key - это поле-ключ, в котором размещается значение ключа, идентифицирующее элемент,

«другие поля» - поля для размещения тех полезных данных, которые должны содержаться в записи.

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

Тип таблицы определим как

TTable = Array [0.. HighIndex] Of TElement; (10.2а)

Тогда сама таблица может быть определена как

Var a: TTable; (10.2б)

иначе говоря, таблица представляется как последовательность элементов а[0], a[1],…, a[HighIndex], каждый из которых является записью типа TElement. Представление таблицы в виде массива необязательно; для нас важен порядок следования элементов, который задается с помощью индекса.

Зададим некоторые переменные:

N, HighIndex: Integer;

где N - количество активных элементов, HighIndex - максимальное значение индекса активного элемента. Индексы вектора а начинаются с нуля, поэтому HighIndex = N - 1.

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

1) index = -1;

2) i:= 0;

3) если a[i].Кey = ArgSearch, то index:= i и переход к п. 6;

4) если a[i].key <> ArgSearch, то i:= i+1 ;

5) если i <= HighIndex, то переход к п. 3;

6) завершение поиска.

Переменная index (порядковый номер, индекс в векторе а) играет роль указателя на найденную запись. Если после завершения поиска index = -1, то поиск неудачен, если index ¹ -1, то поиск результативен, причем искомая запись есть a[index].

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

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

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