Индексно-последовательный поиск
При таком поиске организуется две таблицы: таблица данных со своими ключами (упорядоченная по возрастанию) и таблица индексов, которая тоже состоит из ключей данных, но эти ключи взяты из основной таблицы через определенный интервал (рис. 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; |
