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

　どうも、わくばです！

　今日は Jump Searchです。こちらもソート済みの配列を検索するアルゴリズムです。単純に言うとLinear Searchを端折った感じです。まず決まったintervalで飛び飛びに進んで探索をします。どのintervalにあるかわかったらその中でLinear Searchをして終わりです。

コードは以下のようになりました。

const jumpSearch = (array, value) =>     {

    let { length } = array

    let interval = Math.floor(Math.sqrt(length));

    //これらは区画の両端。上限と下限
    let blockFloor = 0, blockCeil= interval;

    //区画の両端の更新しながら、value以上の上限を持つ区画を探す
    while (array[Math.min(blockCeil, length) - 1] < value)
    {
        //以下2行は区画の更新
        //前回の上限を、今回の下限にする 
        blockFloor = blockCeil;
        //前回の上限にintervalを足して今回の上限にする
        blockCeil += interval;
        
        //最後までなかったらそもそもなかった    
        if (blockFloor >= length)
            return -1;
    }

    //LinearSearch
    /**
     以前僕の記事で紹介した方法は複数マッチを拾うため配列を作って返したが
     今回は一個で良いので、whileで一個見つかるまでループしている
     **/ 
    while (array[blockFloor] < value)
    {
        blockFloor++;

        if (blockFloor == Math.min(blockCeil, length))
            return -1;
    }

    return array[blockFloor] == value ? blockFloor : -1;
}

let array = [1,2,4,6,8,9,90];
console.log(jumpSearch(array,6))
>>>3

　時間計算量は\(O(\sqrt{n})\)です。飛び飛びLinear Searchなので単にルートを取るだけです。Counting Sortのような、配列サイズに依存するメモリの使い方はせず、有限で住むので空間計算量は\(O(1)\)です。

　最近Whileの使い方がなれてきて、すごい便利だなと感じるようになりました。forとifの組み合わせ+必要最低限のループっていう使い方ができるので無駄がありません。

　今日は以上です。

　では。