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

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

     Мы приходим к алгоритму, называемому интерполяционным поиском. Пусть задан массив записей R1,R2,..Rk, снабженных соответственно ключами K1,K2,..Kn. Необходимо найти запись с данным ключом K. Тогда, если известно, что K лежит между Kl и Ku, то следующую пробу делаем примерно на расстоянии (u-l)*(K-Kl)/(Ku-Kl) от l, предполагая, что ключи являются числами, возрастающими приблизительно как арифметическая прогрессия.

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