iT邦幫忙

2021 iThome 鐵人賽

0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 32

【Day32】[演算法]-內插搜尋法Interpolation Search

內插搜尋法(Interpolation Search  ),又稱插補搜尋法,是二分搜尋法的改良版,二分搜尋法是先找出中間值,而內插搜尋法是透過斜率公式來估出資料可能存在的位置,搜尋前也必須先將資料列排序好。

公式如下

https://ithelp.ithome.com.tw/upload/images/20211013/20121027gqrEoCTvTW.jpg


下面利用10 20 30 40 50 60 70 80 90搜尋40為例。
https://ithelp.ithome.com.tw/upload/images/20211013/20121027CvgzhXuanp.jpg


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項

上一篇
【Day31】[演算法]-二分搜尋法Binary Search
下一篇
【Day33】[演算法]-深度優先搜尋DFS與廣度優先搜尋BFS
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言