【Day32】[演算法]-内插搜寻法Interpolation Search

内插搜寻法(Interpolation Search  )，又称插补搜寻法，是二分搜寻法的改良版，二分搜寻法是先找出中间值，而内插搜寻法是透过斜率公式来估出资料可能存在的位置，搜寻前也必须先将资料列排序好。

公式如下

下面利用10 20 30 40 50 60 70 80 90搜寻40为例。

JavaScript

let data = [10,20,30,40,50,60,70,80,90];
let target = 40;

function interpolationSearch(arr, target) {
  let start = 0;
  let end = arr.length - 1;
  let mid;

  while (end >= start) {
    mid = Math.floor((target - arr[start]) * (end - start) / (arr[end] - arr[start]) + start);

    if (arr[mid] === target) {
      return "有搜寻结果: 在第" + (mid + 1) + "项";
    } else {
      if (target > arr[mid]) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
  }
  return "无搜寻结果";
}

console.log(interpolationSearch(data, target)); //"有搜寻结果: 在第4项"

Python

#Interpolation Search

data = [10,20,30,40,50,60,70,80,90]
target = 40
def interpolationSearch(arr, target):
 
    start = 0
    end = len(arr)-1
 
    while start <= end:
        mid = (target - arr[start]) * (end - start) // (arr[end] - arr[start]) + start

        if target == arr[mid]:
            return "有搜寻结果: 在第" + str(mid+1) + "项"
        else:
            if target < arr[mid]:
                end = mid - 1
            else:
                start = mid + 1
    return "无搜寻结果"

print(interpolationSearch(data,target))#有搜寻结果: 在第4项