iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 15
0
自我挑戰組

透過JavaScript學習演算法與資料結構系列 第 15

插補搜尋(Interpolation Search)

  • 分享至 

  • xImage
  •  

插補搜尋(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
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言