Задача реализовать алгоритм интерполяционного поиска

Интерполяционный поиск — это еще один алгоритм «разделяй и властвуй», аналогичный бинарному поиску. В отличие от бинарного поиска, он не всегда начинает поиск с середины. Интерполяционный поиск вычисляет вероятную позицию искомого элемента по формуле:

index = low + [(val-lys[low])*(high-low) / (lys[high]-lys[low])]

В этой формуле используются следующие переменные:

lys — наш входной массив.

val — искомый элемент.

index — вероятный индекс искомого элемента. Он вычисляется как более высокое значение, когда значение val ближе по значению к элементу в конце массива (lys[high]), и более низкое, когда значение val ближе по значению к элементу в начале массива (lys[low]).

low — начальный индекс массива.

high — последний индекс массива.

Алгоритм осуществляет поиск путем вычисления значения индекса:

Если значение найдено (когда lys[index] == val), возвращается индекс.

Если значение val меньше lys[index], то значение индекса пересчитывается по формуле для левого подмассива.

Если значение val больше lys[index], то значение индекса пересчитывается по формуле для правого подмассива.

Решение:

def InterpolationSearch(lys, val):

low = 0

high = (len(lys) - 1)

while low <= high and val >= lys[low] and val <= lys[high]:

index = low + int(((float(high - low) / ( lys[high] - lys[low])) * ( val - lys[low])))

if lys[index] == val:

return index

if lys[index] < val:

low = index + 1;

else:

high = index - 1;

return -1

Если мы используем функцию для вычисления:

»> print(InterpolationSearch([1,2,3,4,5,6,7,8], 6))

Наши начальные значения будут следующими:

val = 6,

low = 0,

high = 7,

lys[low] = 1,

lys[high] = 8,

index = 0 + [(6-1)*(7-0)/(8-1)] = 5

Поскольку lys[5] равно 6, что является искомым значением, мы прекращаем выполнение и возвращаем результат:

5

Если у нас большое количество элементов и наш индекс не может быть вычислен за одну итерацию, то мы продолжаем пересчитывать значение индекса после корректировки значений high и low.

Временная сложность интерполяционного поиска равна O(log log n), когда значения распределены равномерно. Если значения распределены неравномерно, временная сложность для наихудшего случая равна O(n) — так же, как и для линейного поиска.

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

Пишите ваше решение в комментариях?

Источник: vk.com

Комментарии: