Изменения

Пусть <tex> a </tex> {{---}} отсортированный массив чисел из <tex> n </tex> чисел, <tex> x </tex> {{---}} значение, которое нужно найти. Поиск происходит подобно [[Целочисленный двоичный поиск|двоичному поиску]], но вместо деления области поиска на две примерно равные части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Если известно, что <tex> x </tex> лежит между <tex> a_l </tex> и <tex> a_r </tex>, то следующая проверка выполняется примерно на расстоянии <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> (r - l) </tex> от <tex> l </tex>.

Формула для разделительного элемента <tex> m </tex> получается из следующего уравнения: <tex dpi ="170"> \frac{x - a_l}{m - l} = \frac{a_r - a_l}{r - l} </tex> {{---}}откуда следует, что <tex> m = l + </tex> <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> (r - l) </tex>. На рисунке внизу показано, из каких соображений берется такая оценка. Интерполяционный поиск основывается на том, что наш массив представляет из себя что-то наподобии арифметической прогрессии.[[Файл:interpolation_search_from_gshark.png|500px|center|Размещение разделительного элемента]]  == Псевдокод ===<code style = "display: inline-block;"> '''int''' interpolationSearch(na : '''int[]''', xkey : '''int'''):<font color=green> // a должен быть отсортирован </font> l left = 0; <font color=green> // левая граница поиска (будем считать, что элементы массива нумеруются с нуля)</font> r right = n a.length - 1; <font color=green> // правая граница поиска</font>

'''while ''' a[lleft] <= x && x key '''and''' key <= a[rright] m mid = l left + (x key - a[lleft]) * (right - left) / (a[rright] - a[lleft]) * (r - l); <font color=green> // элементиндекс элемента, с которым будем проводить сравнение</font> '''if ''' a[mmid] == x< key result left = m;mid + 1 '''else if ''' a[mmid] < x> key l right = m + mid - 1; '''else''' r = m - 1;'''return''' mid

'''if ''' a[lleft] == xkey result '''return''' left '''else if''' a[right] = l;= key '''return''' right '''else''' result = '''return''' -1; <font color=green>//если такого элемента в массиве нет </ not foundfont>

Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный. Если ключи распределены случайным образом, то за один шаг алгоритм уменьшает количество проверяемых элементов с <tex> n </tex> до <tex> \sqrt n </tex><ref>[http://www.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdf Interpolation Search {{---}} A LogLogN Search]</ref>. То есть, после <tex>k</tex>-ого шага количество проверяемых элементов уменьшается до <tex dpi = 170>n^{\frac{1}{2^k}}</tex>. Значит, остаётся проверить только 2 элемента (и закончить на этом поиск), когда <tex dpi = 150>\frac{1}{2^k} = \log_{n}2 = \frac{1}{\log_{2}n} </tex>. Из этого вытекает, что количество шагов, а значит, и время работы составляет <tex>O(\log \log n)</tex>.

== Литература Примечания==Д.Э. Кнут: [http:<references//books.google.com/books?id=92rW-nktlbgC&pg=PA452&lpg=PA453&ots=jChsP2sutg&dq=%D0%BA%D0%BD%D1%83%D1%82+%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D1%8F%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9+%D0%BF%D0%BE%D0%B8%D1%81%D0%BA&hl=ru&ie=windows-1251&output=html Искусство программирования (том 3)] Wikipedia: [http://en.wikipedia.org/wiki/Interpolation_search Interpolation search] Wikipedia: [http://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA Интерполирующий поиск]>

==Источники информации==* Дональд Кнут {{---}} Искусство программирования. Том 3. Сортировка и поиск. / Knuth D.E. {{---}} The Art of Computer Programming. Vol. 3. Sorting and Searching.*[[Категорияhttp: Дискретная математика и алгоритмы]//en.wikipedia.org/wiki/Interpolation_search Wikipedia {{---}} Interpolation search]*[[Категорияhttp: Алгоритмы поиска]//ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA Википедия {{---}}Интерполирующий поиск]