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

　どうも、わくばです！

　今日はBinary Searchです。ソートが前提の処理ですが、前回のLinear searchより速いと思います。

　仕組みはこんな感じ

1. 基準値を決める
2. 基準値と探している値を比べる
3. 基準値より大きければその基準値より上に的を絞る
4. 基準値より小さければその基準値より下に的を絞る
5. 一個になったらそれが答え

 半分ちょを繰り返して探していくってことですね。

const binarySearch = (array, value) => {

    //まずソート。以前の記事を参照
    const sortedArray = quickSort(array);

    //上限と下限を定義する
    //ここからこの2つの範囲を狭めていきvalueを探す
    let low = 0;
    let high = sortedArray.length - 1;

    //lowとhighが重なるまで実行
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        //基準ともし同じならそいつを返す
        if (sortedArray[mid] === value) {
            return mid;
        } else if (sortedArray[mid] < value) {
            //基準より大きければ、その基準より下はいらないのでlowを上げる
            low = mid + 1;
        } else {
            //小さければ上がいらないのでhighを下げる
            high = mid - 1;
        }
    }
    return -1;
}

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

console.log(binarySearch(array, 144))

>>>10

 　Big O notationについて、今までComplexityと言ったりオーダーと言ったりしていましたが、時間計算量という表現に統一します。時間計算量と空間計算量があるようで、C言語などメモリの扱いを自分で行わなければいけない場合は空間計算量も議論しながらやるようですね。

　今回の時間計算量は、予めソートしてあるとして、純粋にサーチの部分だけ考えると\(O(logn)\)になります。バイナリーで処理が進むイメージがつかめない人はこの動画が非常にわかりやすく説明してくれているので是非参考にしてください。おすすめです。

youtu.be

　以上です。疑問点や誤植などありましたら気軽にお願いします。

　では。