Программирование поискових алгоритмов

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
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 для поиска?
Python очень удобочитаемый и эффективный по сравнению с такими языками программирования, как Java, Fortran, C, C++ и т. д. Одним из ключевых преимуществ использования Python для реализации алгоритмов поиска является то, что вам не нужно беспокоиться о приведении или явной типизации.
В Python большинство алгоритмов поиска, которые мы обсуждали, будут работать так же хорошо, если мы ищем строку. Имейте в виду, что понадобится внести изменения в код для алгоритмов, которые используют искомый элемент для числовых вычислений, например алгоритм интерполяционного поиска.
Python также подходит, если вы хотите сравнить производительность различных алгоритмов поиска для вашего dataset’а. Создание прототипа на
Python проще и быстрее, потому что вы можете сделать больше с меньшим количеством строк кода.
Чтобы сравнить производительность наших реализованных алгоритмов, в Python мы можем использовать библиотеку time: