Метод оптимизации поиска путем перестановки в начало списка.

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

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

q= nil

p = table

while (p <> nil) do

if key = k(p) then

search = p

if q = nil

then 'перестановка не нужна'

return

endif

nxt(q) = nxt(p)

nxt(p) = table

table = p

return

endif

q = p

p = nxt(p)

endwhile

search = 0

return

Этот алгоритм применим как для списков, так и для массивов.

Однако, его не рекомендуется применять для массивов, так как на перестановку элементов массива затрачивается гораздо больше времени, чем на перестановку указателей.

 

Метод транспозиции при оптимизации поиска.

В данном методе найденный элемент переставляется на один элемент к голове списка. И если к этому элементу обращаются часто, то, перемещаясь к голове списка, он скоро окажется на первом месте.

 

 

 

Для реализации данного метода понадобиться уже 3 рабочих указателя

р - рабочий указатель

 

q - вспомогательный указатель, отстает на один шаг от р

 

s - вспомогательный указатель, отстает на два шага от р

 

Алгоритм метода транспозиции

s = nil

q = nil

p = table

while (p <> nil) do

if key = k(p) then

‘ нашли, транспонируем

if q = nil then

‘ переставлять не надо

return

endif

nxt(q) = nxt(p)

nxt(p) = q

if s = nil then

table = p

else

nxt(s) = p

search = p

endif

return

endif

s =q

q = p

p = nxt(p)

endwhile

search = nil

return

 

Этот метод удобен при поиске не только в списках, но и в массивах (так как меняются только два стоящих рядом элемента).

 

Бинарный поиск

 

Бинарный поиск (метод деления пополам)

 

Метод используется только для отсортированных массивов.

 

Основная идея - выбрать случайно некоторый элемент A_M и сравнить его с аргументом поиска Х.

Если A_M=Х, то поиск закончен; если A_M <X, то мы заключаем, что все элементы с индексами, меньшими или равными М, можно исключить из дальнейшего поиска.

 

Аналогично, если A_M >X.

Выбор М совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача - исключить как можно больше элементов из дальнейшего поиска. Оптимальным решением будет выбор среднего элемента, т.е. середины массива.

Рассмотрим пример, представленный на рисунке ниже

 

Допустим необходимо найти элемент с ключом key = 52.

Обозначим:

low - индекс нижней границы интервала поиска

hi - индекс верхней границы интервала поиска

mid - индекс середины интервала поиска

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

low = 1

hi = n

while (low <= hi) do

mid = (low + hi) div 2

if key = k(mid) then

search = mid

return

endif

if key < k(mid) then

hi = mid - 1

else

low = mid + 1

endif

endwhile

search = 0

return

Согласно алгоритму, в нашем примере первым сравниваемым элементом будет 49. Так как 49<52, то ищем следующую середину среди элементов, расположенных выше 49. Это число 86. 86>52, поэтому теперь ищем 52 среди элементов, расположенных ниже 86, но выше 49. На следующем шаге обнаруживаем, что очередное значение середины равно 52. Мы нашли элемент в массиве с заданным ключом.

Количество сравнений при бинарном поиске (эффективность) имеет порядок

 

О(log₂n)

Например, n = 1024.

При последовательном поиске С = 512, а при бинарном
С = 10.

Можно совместить бинарный и индексно-последовательный поиск (при больших объемах данных), учитывая, что последний также используется при отсортированном массиве.