Интерполяционный поиск

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

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

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

По описанию метода, получим блок-схему и код ниже:

Рис. 2.2. Блок-схема Интерполяционного поиска

long IntFind(long array[], long size, long What)

{

long i;

long Found = -1; // найденная позиция

short Lb = 0; // нижняя граница диапазона поиска

short Ub = size-1; // верхняя граница диапахона поиска

while(Lb< Ub) // если верхняя граница станет меньше нижней, то выйдем из цикла

{

// расстояние следующей пробы от Lb

i = Lb + (double)((Ub - Lb)*(Key - array [Lb])) / (double)(array [Ub] - array [Lb]);

if (i< Lb || i> Ub)

break; // выйдем из цикла, если расчитанное расстояние вышло за рамки

if(Key< array [i]) //если ключ меньше текущей позиции

Ub = i-1; //то устанавливаем новую верхнюю границу

else

if(Key> array [i]) //если ключ больше текущей позиции

Lb=i+1; // то устанавливаем новую нижнюю границу

else { // если не больше и не меньше, т.е. равно

Found = i; // запоминаем, найденную позицию

break; // и выходм из цикла

}

}

return Found;

}