JavaScriptでの補間検索

補間検索

補間検索は、キーに割り当てられた数値（キー値）で並べ替えられた配列内のキーを検索するためのアルゴリズムです。

例

n個の一様分布値arr[]のソートされた配列があり、配列内の特定の要素ターゲットを検索する関数を作成する必要があるとします。

位置を見つけるために次の操作を行います-

//式の考え方は、より高い値のposを返すことです

//検索する要素がarr[hi]に近い場合。そして

// arr [lo]

pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo]))

キー-

• arr[]-要素を検索する必要がある配列

• x-検索する要素

• lo-arr []

  の開始インデックス

• hi-arr []

  の終了インデックス

最初の引数として数値の配列を取り、2番目の引数として検索ターゲットを受け取るJavaScript関数を作成する必要があります。

この関数は、補間検索アルゴリズムを使用して、配列内のターゲットを検索する必要があります。

例

以下はコードです-

const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const target = 25;
const interpolationSearch = (arr = [], target) => {
   let left = 0;
   let right = arr.length - 1;
   while (left <= right) {
      const rangeDelta = arr[right] - arr[left];
      const indexDelta = right - left;
      const valueDelta = target - arr[left];
      if (valueDelta < 0) {
         return -1;
      }
      if (!rangeDelta) {
         return arr[left] === target ? left : -1;
      }
      const middleIndex = left + Math.floor((valueDelta * indexDelta) / rangeDelta);
      if (arr[middleIndex] === target) {
         return middleIndex;
      }
      if (arr[middleIndex] < target) {
         left = middleIndex + 1;
      } else {
         right = middleIndex - 1;
      }
   };
   return -1;
};
console.log(interpolationSearch(arr, target));

出力

以下はコンソールでの出力です-

10