=== Идея ===Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чем чём разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного поиска не делают различий между "немного больше" и "существенно больше".
=== Алгоритм ===[[Файл:Search.jpg|thumb|300px|Нахождение медианы]]Пусть <tex> a </tex> {{--- }} отсортированный массив чисел из <tex> n </tex> чисел, <tex> x </tex> {{- --}} значение, которое нужно найти.Поиск происходит подобно [[Целочисленный двоичный поиск|двоичному поиску]], но вместо деления области поиска на две примерно равные части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Если известно, что <tex> x </tex> лежит между <tex> a_l </tex> и <tex> a_r </tex>, то следующая проверка выполняется примерно на расстоянии <tex dpi = "180170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> (r - l) </tex> от <tex> l </tex>.
=== Время работы ===При условии, что значения элементов близки к арифметической прогрессии, за один шаг алгоритм уменьшает количество проверяемых элементов с Формула для разделительного элемента <tex> n m </tex> до получается из следующего уравнения: <texdpi = "170"> \sqrt n frac{x - a_l}{m - l} = \frac{a_r - a_l}{r - l} </tex>. {{---}}откуда следует, что <tex> m = l + <br/tex>Поэтому среднее время работы алгоритма: <texdpi = "170"> O(\log frac{x - a_l}{a_r - a_l} \log n) cdot</tex>. <br/>При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до <tex> O(nr - l) </tex>.На рисунке внизу показано, из каких соображений берется такая оценка. Интерполяционный поиск основывается на том, что наш массив представляет из себя что-то наподобии арифметической прогрессии.[[Файл:interpolation_search_from_gshark.png|500px|center|Размещение разделительного элемента]]
=== Реализация =Псевдокод ==Приведем код функции <texcode> \mathrm{interpolation\_search '''int''' interpolationSearch(a: '''int[]''', n, xkey : '''int''')} <font color=green> /tex/ a должен быть отсортирован </font> на языке C++. left = 0 <codefont color=green> int interpolation_search// левая граница поиска (double* a, int nбудем считать, double xчто элементы массива нумеруются с нуля) {</font> int l right = 0; int r = n a.length - 1; int m;<font color=green> // правая граница поиска </font>
'''while (''' a[lleft] <= x && x key '''and''' key <= a[rright]) { mid = l left + (x key - a[lleft]) * (right - left) / (a[rright] - a[lleft]) * (r <font color=green> // индекс элемента, с которым будем проводить сравнение </font> '''if''' a[mid] < key left = mid + 1 '''else if''' a[mid] > key right = mid - l);1 '''else''' '''return''' mid
'''if (''' a[mleft] == x)key '''return m;''' left '''else if (''' a[mright] < x) l = m + 1;= key '''return''' right '''else''' r '''return''' -1 <font color= m green>// если такого элемента в массиве нет </font></code> == Время работы ==Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный. Если ключи распределены случайным образом, то за один шаг алгоритм уменьшает количество проверяемых элементов с <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>. } При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до <tex> O(n) </tex>. if Эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (aпока таблица не очень велика). Кроме того, типичные таблицы недостаточно случайны, да и разница между значениями <tex>\log \log n</tex> и <tex>\log n</tex> становится значительной только при очень больших <tex>n</tex>. На практике при поиске в больших файлах оказывается выгодным на ранних стадиях применять интерполяционный поиск, а затем, когда диапазон существенно уменьшится, переходить к двоичному. ===Пример работы вместе с сравнением с бинарным поиском===[[lФайл:ip_vs_bin_from_gshark.png|700px|center|Сравнение бинарного и интерполирующего поисков]] ==Примечания== x) return l;<references/> else==Источники информации== return * Дональд Кнут {{---}} Искусство программирования. Том 3. Сортировка и поиск. / Knuth D.E. {{---1; }} The Art of Computer Programming. Vol. 3. Sorting and Searching.*[http://en.wikipedia.org/wiki/ not found Interpolation_search Wikipedia {{---}}Interpolation search] <*[http://ru.wikipedia.org/wiki/code>%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 Википедия {{---}} Интерполирующий поиск]
=== Полезные ссылки ===Д.Э. Кнут: [http[Категория://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)Дискретная математика и алгоритмы]] <br/>Wikipedia: [http[Категория://en.wikipedia.org/wiki/Interpolation_search Interpolation searchАлгоритмы поиска]]
