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

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

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

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

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

Алгоритмы поиска занимают важное место в прикладных алгоритмах. Обычно данные хранятся в определенном образом упорядоченном наборе. Найти некоторую запись из этого набора — вот классическая задача программирования, вокруг которой сгенерировано множество идей [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]. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой и правой частях массива. Алгоритм определяется рекурсивно, однако на практике применяется нерекурсивная версия ввиду её большой эффективности.