Изменения

=== Идея ===Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чем чём разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного поиска не делают различий между "немного больше" и "существенно больше".

=== Алгоритм ===

Пусть <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} </tex> от <tex> l </tex>.

=== Время работы Псевдокод ===При условии, что значения элементов близки к арифметической прогрессии, за один шаг алгоритм уменьшает количество проверяемых элементов с <tex> n </tex> до <tex> \sqrt n </tex>. <br/>Поэтому среднее время работы алгоритма: <tex> O(\log \log n) </tex>. <br/>При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до <tex> O(n) </tex>.

==Время работы = Полезные ссылки =Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный. Если ключи распределены случайным образом, то за один шаг алгоритм уменьшает количество проверяемых элементов с <tex> n </tex> до <tex> \sqrt n </tex>. То есть, после <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>. == Литература ==