iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 15
0

插補搜尋(Interpolation Search)演算法又稱為內插搜尋演算法,是二元搜尋(Binary Search)演算法的變體。這套演算法可以在已排序好的序列中根據資料的預測線或近似線來進行高效率的搜尋,近似線愈精準,搜尋的效率就愈高。

img

依照公式程式碼如下:

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

  while (end >= start) {
      let m = Math.floor((key - arr[start]) * (end - start) / (arr[end] - arr[start]) + start);

      if (m > end || m < start) {
          break;
      }

      if (arr[m] === key) {
          return m;
      } else {
          if (key > arr[m]) {
              start = m + 1;
          } else {
              end = m - 1;
          }
      }
  }

  return -1;
}

const arr=[0,1,2,3,4,5,6,7,8,9];
console.log(interpolationSearch(arr,3));

上一篇
二元搜尋樹(Binary Search Tree)
下一篇
陣列(Array)
系列文
透過JavaScript學習演算法與資料結構30

尚未有邦友留言

立即登入留言