69
правок
Изменения
Нет описания правки
'''return''' -1 <font color=green>// если такого элемента в массиве нет </font>
</code>
== Время работы ==
Эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (пока таблица не очень велика). Кроме того, типичные таблицы недостаточно случайны, да и разница между значениями <tex>\log \log n</tex> и <tex>\log n</tex> становится значительной только при очень больших <tex>n</tex>. На практике при поиске в больших файлах оказывается выгодным на ранних стадиях применять интерполяционный поиск, а затем, когда диапазон существенно уменьшится, переходить к двоичному.
===Пример работы вместе с сравнением с бинарным поиском===
[[Файл:ip_vs_bin_from_gshark.png|700px|center|Сравнение бинарного и интерполирующего поисков]]
==Примечания==
* Дональд Кнут {{---}} Искусство программирования. Том 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 Википедия {{---}}Интерполирующий поиск] [[Категория: Дискретная математика и алгоритмы]][[Категория: Алгоритмы поиска]]
