【アルゴリズム(JS実装) 】Interpolation Search

　どうも、わくばです！

　今日はInterpolation Searchです。このアルゴリズムはBinary Searchの改造版で基本的な考え方は同じです。したがってソート済みの配列に適用する点は同じです。では何が違うのかというと、Binaryでは真ん中で半分にしていましたが、Interpolationでは分割点をもっと正確に計算しているという点です。確かに、何も考えずに真ん中で分けるのはあまりスマートではないですよね。せっかくソート済みなんだからもう少し絞れるだろ、というわけです。「あいさつ」という言葉を国語辞典で調べる場合、真ん中を開くことはしませんよね。あ行のように明らかに近いところを開くはずです。これと同じ発想です。

　ではその分割点はどう決めるのかというと以下の式で決めます。

\(position(x) = low +  \dfrac{x-array[low]}{array[high]-array[low]}(high-low) \)

　ちょっとわかりにくいかもしれませんが言ってることは単純で、\(\dfrac{x-array[low]}{array[high]-array[low]}\)の部分で\(x\)を0〜1の縮尺に圧縮して、\((high-low)\)をかけてインデックスに変換しています。

以下がコードです。

const interpolationSearch = (array, value) => {
    const { length } = array;
    let low = 0;
    let high = length - 1;
    let position;
    let delta;
    while (
        low <= high &&
        value >= array[low] &&
        value <= array[high]
    ) {
        //valueを圧縮
        delta = (value - array[low]) / (array[high] - array[low]); 
        //positionを計算
        position = low + Math.floor((high - low) * delta); 
        //ぴったり賞ならそれを返す
        if (array[position] == value) { 
            return position;
        }
        //positionが目的のvalueの位置より左にあれば右に詰める
        if (array[position] < value) { 
            low = position + 1;
        } else {
        //positionが目的のvalueの位置より右にあれば左に詰める
            high = position - 1;
        }
    }
    return -1;
}

const array = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19];
interpolationSearch(array, 16)

 　時間計算量は平均で\(O(log(logn))\)になるようです。理由についてですが、かなり調べましたが正直シャープな説明はありませんでした。唯一以下の論文を見つけたのですが、ちょっと難しくて完全には負いきれませんでした(笑)

https://www.cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/17.pdf

　ただ論文に目を通した感じ、\(n=z^{2^k}\)として仮定して上から抑える形で算出していたので、\(O(log(logn))\)のうち片方はBinary処理によるもんですが、もう一方は仮定によって生まれているものだと思います。

　Binary Searchよりも処理が少ないってことがわかれば良いのかな、、、すんません(汗)

　今日は以上です。では。