Алгоритм интерполяционного поиска является улучшенной версией бинарного поиска.

Поскольку его временная сложность составляет O (log log n), тогда как временная сложность двоичного поиска составляет O (log n).

Его следует использовать, когда массив отсортирован и имеет равномерно распределенные значения.

Как мы видели в бинарном поиске, мы начинаем с середины списка/массива, а затем сравниваем элемент со средним элементом и определяем, меньше он или больше. соответственно, мы выбираем подмассив, который будем искать дальше. Обратитесь к изображению ниже. (код для binarysearch)

При интерполяционном поиске мы используем формулу, которая будет использоваться для позиции, известную как формула положения зонда.

pos = начало + [ ( (конец-начало) / a[конец] -a[начало] ) * (вход -A[начало])]

поэтому pos – это индекс, с которого начнется поиск.

Теперь нам нужно иметь определенные переменные для нашего алгоритма

N = длина массива

начало = 0

конец = N-1

  1. мы проверяем, если Arr[pos] == input , возвращаем pos
  2. если arr[pos] ‹ элемент, start = pos + 1
  3. если элемент arr[pos] ›, end = pos-1
  4. повторить 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”)

Репозиторий алгоритмов