Структуры и алгоритмы обработки данных

       

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


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

Сначала производится последовательный поиск в таблице индексов по заданному аргументу поиска. Как только мы проходим ключ, который оказался меньше заданного, то этим мы устанавливаем нижнюю границу поиска в основной таблице - low, а затем - верхнюю - hi , на которой ( kind > key ).

Например, key = 101.

Поиск идет не по всей таблице, а от low  до hi.

Примеры программ:

Псевдокод:

i = 1

while (i <= m) and (kind(i) <= key) do

  i=i+1

endwhile

if i = 1 then low = 1

  else low = pind(i-1)

endif



if i = m+1 then hi = n

  else hi = pind(i)-1

endif

for j=low to hi

  if key = k(j) then

    search=j

    return

  endif

next j

search=0

return

Паскаль:

i:=1;

while (i <= m) and (kind[i] <= key) do

  i=i+1;

if i = 1 then low:=1 else low:=pind[i-1];

if i = m+1 then hi:=n else hi:=pind[i]-1;

for j:=low to hi do

  if key = k[j] then

    begin   

      search:=j;

      exit;

    end;

search:=0;

exit;



Содержание раздела