Алгоритм поиска

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

Алгоритм последовательного поиска

Последовательный поиск

Введение в поиск

Алгоритмы поиска занимают важное место в прикладных алгоритмах. Обычно данные хранятся в определенном образом упорядоченном наборе. Найти некоторую запись из этого набора — вот классическая задача программирования, вокруг которой сгенерировано множество идей [1, 3, 9, 10, 13].

Пусть мы имеем таблицу, состоящую из записей (табл. 3.1). Первое поле каждой записи содержит ключ (например, табельный номер); второе — фамилию и так далее. Ключом может любое поле записи.

Таблица 3.1

	Иванов
	Андреев
	Сидоров
	Петров

Основная задача поиска — найти запись с заданным ключом.

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

Наиболее примитивный, а значит, и наименее эффективный, способ поиска— это обычный последовательный просмотр записей таблицы [9,11]. Метод применяется к таблице, организованной как массив. Предложим, что к — массив из п ключей; г — массив записей такой, что k(i) — ключ для записи r(i); key — аргумент поиска. Запишем в переменную search наименьшее целое число /, такое, что k(i) = key, если такое / существует, и -1 в противном случае.

for (search=-l, i=0;	i<n;	i + +)
if(key == k[i])
{
search=i;
break;
}

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

На подобной идее основан и метод перемещения в начало: каждый запрос к записи сопровождается её перемещением в начало таблицы; в итоге в начале таблицы оказываются записи, используемые в последнее время.

Все реально применяемые методы поиска относятся к отсортированным таблицам. Для упорядоченной таблицы наиболее эффективными являются: 1) индексно-последовательный поиск и 2) бинарный поиск.

Индексно-последовательный поиск. В дополнение к отсортированной таблице заводится вспомогательная таблица, называемая индексной [9, 11]. Каждый элемент индексной таблицы состоит из ключа и указателя на запись в основной таблице, соответствующую этому ключу kindex. Элементы в индексной таблице, так же как элементы в основной таблице, должны быть отсортированы по этому ключу. Если индекс имеет размер, составляющий одну восьмую от размера основной таблицы, то каждая восьмая запись основной таблицы будет представлена в индексной таблице (рис. 3.1).

Алгоритм индексно-последовательного поиска прост. Предположим, что к — массив из п ключей; г — массив записей такой, что k(i) является ключом для записи r(i); key — аргумент поиска. Пусть — массив ключей в индексе; pindex — массив указателей в индексе на записи. Размер основной таблицы — п. Размер индексной таблицы — indsize.

i = 0;
while ((	i < ind size)	&& (kindex	[i] <= key))
i + +;
/^установить low на	наименьшую	возможную позицию
элемента	в массиве*/
if(i ==	0)
low=	0;
else
low	= pindex[i^	;
/^установить high	на	наибольшую	возможную
позицию	элемента в	массиве*/

if (i==ind_size)

high=n; else

high=pindex[i];

/*поиск в массиве от low до high*/

for (j=low, search= if (k[j]==key)

{

search=j; breake;

■1; j<high; j+ +

Основная таблица

Индексная таблица

kindex pindex

I L

k r i ключ запись I

8 ] - ^------- ч------ >

14 ] i ^--------- т--------- s

26,s \ ------------ ^----------- <.

38 1У v--------- ^-------- ^ i s

72 ] S

I PJ 115 I oo ^------------ ^----------- ч i

306 I I ^------------ ^----------- ч

• 321 ]

329 1 ^------------ т----------- >

387 I ----------------------------------- -> i

.409. ]|

LS12 _L)]

540 1 I ч------------ ч----------- ч

567 ) \ ------------- *------------ 4

1 583 1 *----------------- *---------------- * i

5d2 1 ^----------- ^----------- ^

1--------- 1-------- h ' ■ ■ ■ i ч--------- ^------- гУ i

Рис. З.1. Схема хранения информации при индексно-последовательном поиске

Достоинство алгоритма заключаются в том, что сокращаются время поиска, так как последовательный поиск первоначально ведется в индексной таблице, имеющей меньший размер, чем основная таблица; когда найден правильный индекс, второй последовательный поиск выполняется по небольшой части записей основной таблицы.

Бинарный поиск. Аргумент сравнивается с ключом среднего элемента в массиве [9, 11]. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой и правой частях массива. Алгоритм определяется рекурсивно, однако на практике применяется нерекурсивная версия ввиду её большой эффективности.

Дата добавления: 2014-11-29