Изменения

Перейти к: навигация, поиск

Интерполяционный поиск

14 байт добавлено, 18:25, 17 мая 2012
Другая картинка
== Алгоритм ==
[[Файл:SearchInterpolation_search.jpgpng|thumb|300px350px|Нахождение разделительного элемента]]
Пусть <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} \cdot</tex> <tex> (r - l) </tex> от <tex> l </tex>.
170
правок

Навигация