Алгоритм интерполяционного поиска является улучшенной версией бинарного поиска.
Поскольку его временная сложность составляет O (log log n), тогда как временная сложность двоичного поиска составляет O (log n).
Его следует использовать, когда массив отсортирован и имеет равномерно распределенные значения.
Как мы видели в бинарном поиске, мы начинаем с середины списка/массива, а затем сравниваем элемент со средним элементом и определяем, меньше он или больше. соответственно, мы выбираем подмассив, который будем искать дальше. Обратитесь к изображению ниже. (код для binarysearch)
При интерполяционном поиске мы используем формулу, которая будет использоваться для позиции, известную как формула положения зонда.
pos = начало + [ ( (конец-начало) / a[конец] -a[начало] ) * (вход -A[начало])]
поэтому pos – это индекс, с которого начнется поиск.
Теперь нам нужно иметь определенные переменные для нашего алгоритма
N = длина массива
начало = 0
конец = N-1
- мы проверяем, если Arr[pos] == input , возвращаем pos
- если arr[pos] ‹ элемент, start = pos + 1
- если элемент arr[pos] ›, end = pos-1
- повторить 1–3
поэтому на изображении ниже мы видим, что только за одну итерацию найдено положение x = 2.
# -*- coding: utf-8 -*- “”” Created on Wed Aug 21 17:00:45 2019 @author: amit “”” def interpolationSearch(arr,n,x): start = 0 end = (n-1) while start <= end and x >= arr[start] and x <= arr[end]: if start == end: if arr[start] == x: return start; return -1; pos = start + int(((float(end — start)/(arr[end]-arr[start]))*(x -arr[start]))) if arr[pos] == x: return pos; if arr[pos] < x : start = pos + 1; else: end = pos -1 ; return -1; # Array of items oin which search will be conducted arr = [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47] n = len(arr) x = 18 # Element to be searched index = interpolationSearch(arr, n, x) index =1 if index != -1: print( “Element found at index”,index ) else: print( “Element not found”)