Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Интерполяционный поиск элемента в массиве

Автор: Илья Кантор
Источник: 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 операций, если данные распределены равномерно. Как правило, он используется лишь на очень больших таблицах, причем делается несколько шагов интерполяционного поиска, а затем на малом подмассиве используется бинарный или последовательный варианты.

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

1.
93K
08 июня 2014 года
Анатолий Шабунио
0 / / 08.06.2014
+2 / -0
Мне нравитсяМне не нравится
8 июня 2014, 14:50:37
вот работающий код на Pascal:

Код:
b:=false; // флаг найденного элемента

        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;
2.
15K
27 декабря 2008 года
BashOrgRu
3 / / 27.12.2008
+3 / -0
Мне нравитсяМне не нравится
23 марта 2010, 10:11:23
Текст содран с книги Кнут, Искусство программирования, т. 3 без указания источника. Код неправильный, компилиться и работать не будет.
3.
27K
11 марта 2007 года
abvgd
0 / / 11.03.2007
+3 / -2
Мне нравитсяМне не нравится
11 марта 2007, 10:14:06
umnik hrenov, esli ti govorit' s lyud'mi normal'no ne umeesh, to chto ti voobshe iz sebya predstavlyaesh, nadibil pereveril i vilogil, eto ne zasluga
4.
24K
30 ноября 2006 года
Оранок
0 / / 30.11.2006
+1 / -2
Мне нравитсяМне не нравится
30 ноября 2006, 19:46:16
напишите пожалуйста полностью алгоритм методом интерполяционного поиска, он мне очень нужен, но разобраться я не могу
5.
19K
12 июня 2006 года
Taras55
0 / / 12.06.2006
+2 / -2
Мне нравитсяМне не нравится
14 июня 2006, 21:34:34
>Не понял: что значит XK]?
Если идею не понял - значит тебе сюда рано,
а если тебе код важнее идеи, то тебе в разделе "Алгоритмы" не место...

>Чем метод отличается от деления пополам (метода вилки)?
Сложностю: log log N < log N
если тебе єто ни про что не говорит, значит для тебя нет алгоритма лучше линейного поиска
6.
534
19 января 2006 года
HarryAxe
448 / / 19.01.2006
+2 / -1
Мне нравитсяМне не нравится
6 июня 2006, 17:11:32
Первыйнах!!!
Не понял: что значит XK]?
Чем метод отличается от деления пополам (метода вилки)?
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог