【アルゴリズム(JS実装)】Exponential Search - 医学生わくばの欲張り技術ブログ

どうも、わくばです！

　今日はExponential Searchです。Exponentialといのは指数関数的という意味です。理系学生は$e^x$や$exp(x)$でおなじみですよね。

　このアルゴリズムは名前の通りで、指数関数的なインターバルを用いて飛び飛びに探索していくアルゴリズムです。Jump Searchと発想は近いと思いますが、Exponential Searchdでは最終的にBinary Searchを用いるので速いです。

　以前記事にしたBinary Searchを添付しておきますので参考にしてみてください。

pyecracker99.hatenablog.com

　以下がコードです。

//まずbinarySearchを定義
const binarySearch = (array, low, high, value) => {

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (array[mid] === value) {
            return mid;
        } else if (array[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}


const exponentialSearch = (array, value) => {
    const { length } = array;

    if (array[0] == value) {
        return 0;
    }

    //valueを超えるタイミングを2の塁乗で探していく
    //1,2,4,8,16,32と増加していく
    let i = 1;
    while (i < length && array[i] < value) {
        i *= 2;
    }

    /**
    iは最初にvalueを通り過ぎた地点なので,
    iはvlaueがある区画の終端で、i\2は始端を表す。
    したがって、binarySearchのlowはi/2を入れる。
    iにしていまうとvalueを通り過ぎたところから右へ
    探索することになるので一生見つからない。
    **/
    return binarySearch(array, i/2, Math.min(i, length-1), value)
}

const array = [12,14,5,1,2,3,4,6,8,0,144,166];

console.log(exponentialSearch(array, 167));
console.log(exponentialSearch(array, 144));
>>>-1
>>>10

　$i = 2^j$である区画$2^{j-1}\sim$2^jの間)にvalueが存在した場合、$j$が処理回数ですから

$$ i = 2^j $$

$$ log(i) = log2^j $$

$$ j = log(i)$$

よってBinary Searchの前までが正確に$O(logi)$かかったと言えます。

　Binary Searchは$2^{j-1}\sim2^j$の間で実行され、これは$$2^{logi}-2^{logi-1} =2^{logi}(2-1)=2^{logi-1} $$よりサイズ$2^{logi-1} $の配列において実行されることになる。

　Binary Searchはサイズｎの配列において$O(logn)$かかるので、$O(log(2^{logi-1})) \approx O(logi)$

　全体で$O(logi)+O(logi)=O(logi)$になります。

　今日は以上です。

　では。