СР 8 Інтерполяційний пошук

Інтерполяційний пошук працює лише у впорядкованому масиві. Заснований він на тому ж принципі, що і алгоритм швидкого пошуку, але більш інтелектуально підходить до поділу масиву на частини. У швидкому пошуку масив на кожному кроці ділиться рівно на 2 половини, а в інтерполяційному враховуються значення крайніх елементів і шуканого елемента.

Допустимо, ми шукаємо число 3 у списку:

1, 3, 5, 55, 66, 77, 567, 545, 12222, 43323

Алгоритм быстрого поиска найдет нужный элемент, за счет того, что уже на первом шаге от отсечет половину списка. Число 567 больше чем  , значит числа  не может быть в правой части списка (список же упорядоченный).

Интерполяционный поиск найдет результат еще быстрее, так как он учитывает значения элементов. На самом деле, число 3 сильно меньше чем 43323 , значит число 3 с большей вероятностью находится где-то в начале списка. Этот алгоритм учитывает значения элементов для выбора опорного элемента, при этом использует такую формулу:

Блок-схема відповідного алгоритма: