69
правок
Изменения
Нет описания правки
'''return''' -1 <font color=green>// если такого элемента в массиве нет </font>
</code>
==Пример работы вместе с сравнением с бинарным поиском==
[[Файл:ip_vs_bin_from_gshark.png|900px|center|Сравнение бинарного и интерполирующего поисков]]
== Время работы ==
Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный. Если ключи распределены случайным образом, то за один шаг алгоритм уменьшает количество проверяемых элементов с <tex> n </tex> до <tex> \sqrt n </tex>(доказательство<ref>[http://www.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdfInterpolation 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>.
Эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (пока таблица не очень велика). Кроме того, типичные таблицы недостаточно случайны, да и разница между значениями <tex>\log \log n</tex> и <tex>\log n</tex> становится значительной только при очень больших <tex>n</tex>. На практике при поиске в больших файлах оказывается выгодным на ранних стадиях применять интерполяционный поиск, а затем, когда диапазон существенно уменьшится, переходить к двоичному.
==Примечания==
