GetInfo.Ru – Компьютерная библиотека
Последние поступления
Как выбрать систему управления базы данных
Базы данных03/09/14
Этапы загрузки UNIX (в схеме)
Unix27/03/12
Gatewall Antispam: тотальный контроль электронной почты
Спам21/04/11
Мастер-класс: создаем Интернет-магазин (Часть 1)
Обзоры ПО20/04/11
CorelDRAW Graphics Suite X5: Что нового?
Обзоры ПО20/07/10
Добавить статью
Самые читаемые материалы
Мягкие вычисления(45582)
Эволюционные вычисления(31718)
Сортировка и поиск: Рецептурный справочник(30635)
Алгоритмы архивации данных(24895)
Методика создания индексных файлов для осуществления полнотекстового поиска в сети Интернет(19394)
Всего статей: 793Всего авторов: 364Подразделов: 47Добавлено за сутки: 0
Статьи  СТАТЬИ Форум  ФОРУМ Рейтинг  РЕЙТИНГ Поиск  ПОИСК Контакты  КОНТАКТЫ
» Главная » Алгоритмы » Интерполяционный поиск элемента в массиве

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


Ilia Kantor
algolist@manual.ru
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(X<K[i]]  u=i-1;
    else if(X>K[i]] l=i+1;
    else НАШЛИ, X==K[i].
}
Не нашли.

Интерполяционный поиск работает за log log N операций, если данные распределены равномерно. Как правило, он используется лишь на очень больших таблицах, причем делается несколько шагов интерполяционного поиска, а затем на малом подмассиве используется бинарный или последовательный варианты.

 
18.02.2003
Версия для печати Версия для печати Запомнить ссылку Запомнить ссылку
Ваша оценка:  1   2   3   4   5     

 О проектеПерепечаткаАвторамПартнерыО нас пишут
Наверх
©2003—2007. GETINFO.RU. ВСЕ ПРАВА ЗАЩИЩЕНЫ.