Интерполяционный поиск элемента в массиве
Источник: http://algolist.manual.ru/
Представьте себе, что Вы ищете слово в словаре. Маловероятно, что Вы сначала загляните в середину словаря, затем отступите от начала на 1/4 или 3/4 и т.д, как в бинарном поиске.
Если нужное слово начинается с буквы 'А', вы наверное начнете поиск где-то в начале словаря. Когда найдена отправная точка для поиска, ваши дальнейшие действия мало похожи на рассмотренные выше методы.
Если Вы заметите, что искомое слово должно находиться гораздо дальше открытой страницы, вы пропустите порядочное их количество, прежде чем сделать новую попытку. Это в корне отличается от предыдущих алгоритмов, не делающих разницы между 'много больше' и 'чуть больше'.
Мы приходим к алгоритму, называемому интерполяционным поиском: Если известно, что К лежит между Kl и Ku, то следующую пробу делаем на расстоянии (u-l)(K-Kl)/(Ku-Kl) от l, предполагая, что ключи являются числами, возрастающими приблизительно в арифметической прогрессии.
// Поиск в массиве K[1..N] числа X интерполяционным поиском
l=1; u=N;
while(u>=l) {
i=l+¦(u-l)*(X-K[l])/(K[u]-K[l]);
if(XK[i]] l=i+1;
else НАШЛИ, X==K[i].
}
Не нашли.
Интерполяционный поиск работает за log log N операций, если данные распределены равномерно. Как правило, он используется лишь на очень больших таблицах, причем делается несколько шагов интерполяционного поиска, а затем на малом подмассиве используется бинарный или последовательный варианты.
Оставить комментарий
Комментарии
L:=1;
R:=length(a);
While (a[L]<=rnd) and (rnd<=a[R]) do begin
i:=L+abs(round((rnd-a[L])/(a[R]-a[L])*(R-L)));
if rnd<a then R:=i-1 else
if rnd>a then L:=i+1 else begin
b:=true;
break;
end;
end;
Если идею не понял - значит тебе сюда рано,
а если тебе код важнее идеи, то тебе в разделе "Алгоритмы" не место...
>Чем метод отличается от деления пополам (метода вилки)?
Сложностю: log log N < log N
если тебе єто ни про что не говорит, значит для тебя нет алгоритма лучше линейного поиска
Не понял: что значит XK]?
Чем метод отличается от деления пополам (метода вилки)?