Поиск в строках, массивах, последовательностях.

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

Представьте себе, что Вы ищете слово в словаре. Маловероятно, что Вы сначала загляните в середину словаря, затем отступите от начала на 1/4 или 3/4 и т.д, как в бинарном поиске.

Если нужное слово начинается с буквы 'А', вы наверное начнете поиск где-то в начале словаря. Когда найдена отправная точка для поиска, ваши дальнейшие действия мало похожи на рассмотренные выше методы.

Если Вы заметите, что искомое слово должно находиться гораздо дальше открытой страницы, вы пропустите порядочное их количество, прежде чем сделать новую попытку. Это в корне отличается от предыдущих алгоритмов, не делающих разницы между 'много больше' и 'чуть больше'.

Мы приходим к алгоритму, называемому интерполяционным поиском: Если известно, что К лежит между K_l и K_u, то следующую пробу делаем на расстоянии (l-u)(K-K_l)/(K_u-K_l) от l, предполагая, что ключи являются числами, возрастающими приблизительно в арифметической прогрессии.

Вверх по странице, к оглавлению и навигации.