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

 

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