Интерполяционный поиск — это еще один алгоритм «разделяй и властвуй», аналогичный бинарному поиску. В отличие от бинарного поиска, он не всегда начинает поиск с середины. Интерполяционный поиск вычисляет вероятную позицию искомого элемента по формуле:
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) — так же, как и для линейного поиска.
Интерполяционный поиск лучше всего работает на равномерно распределенных, отсортированных массивах. В то время как бинарный поиск начинает поиск с середины и всегда делит массив на две части, интерполяционный поиск вычисляет вероятную позицию элемента и проверяет индекс, что повышает вероятность нахождения элемента за меньшее количество итераций.
👉 Пишите ваше решение в комментариях👇
@python_job_interview