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

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

Эффективность индексно-последовательного поиска

Если считать равновероятным появление всех случаев, то эффективность поиска можно рассчитать следующим образом:

Введем обозначения: m- размер индекса; m=n/p, где p- размер шага.

Тогда:

Q=(m+1)/2+(p+1)/2=(n/p+1)/2 +(p+1)/2=n/2p+p/2+1

Продифференцируем Q по p и приравняем производную нулю:

dQ/dp=(d/dp)(n/2p+p/2+1)=-n/2p² +1/2=0

Отсюда p²=n; p_опт=

Подставим p_опт в выражение для Q, получим следующее количество сравнений:

Q= +1

Порядок эффективности индексyо-последовательного поиска Q().