170
правок
Изменения
Нет описания правки
== Алгоритм ==
[[Файл: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 = "170"> \frac{x - a_l}{a_r - a_l} </tex> от <tex> l </tex>.
=== Псевдокод ===
<code>
while (a[l] <= x && x <= a[r]) { m = l + (x - a[l]) / (a[r] - a[l]) * (r - l); // элемент, с которым будем проводить сравнение if (a[m] == x) return result = m; if (a[m] < x)
l = m + 1;
else
r = m - 1;
if (a[l] == x) return result = l;
else
</code>
При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до <tex> O(n) </tex>.
Эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (пока таблица не очень велика). Кроме того, типичные таблицы недостаточно случайны, да и разница между значениями <tex>\log \log n</tex> и <tex>\log n</tex> становится значительной только при очень больших <tex>N</tex>. На практике при поиске в больших файлах оказывается выгодным на ранних стадиях применять интерполяционный поиск, а затем, когда диапазон существенно уменьшится, переходить к двоичному.
== Литература ==
Д.Э. Кнут: [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]
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 Интерполирующий поиск]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы поиска]]
