JavaScript による二分探索法(バイナリサーチ)実装

スポンサーリンク

アルゴリズムを、はじめようを参考に、JavaScript を用いて二分探索法を実装してみました。

<button onclick="buttonClicked()">buttonClicked()</button>

<script>
    var array = [11, 13, 17, 19, 23, 29, 31];
    // 検索対象
    const target = 19;

    function buttonClicked() {
        // 先頭
        let top = 0;
        // 末尾
        var end = array.length;
        search(top, end);
        console.log('process completed.');
    }

    function search(top, end) {
        // 注意: top > end だと、top と end が同じ時に無限ループとなってしまう。
        // よって、判定条件は >= とする。
        if (top >= end) {
            console.log('not found...');
            return;
        }
        // 中央位置
        let middle = parseInt((top + end) / 2, 10);

        if (target === array[middle]) {
            console.log('target found', target);
            return;
        } else {
            if (target < array[middle]) {
                // 中央位置の値よりも、検索対象の値が小さい場合 => 検索対象を前半分
                end = middle;
                search(top, end);
            } else if (target > array[middle]) {
                // 中央位置の値よりも、検索対象の値が大きい場合 => 検索対象を後ろ半分
                top = middle + 1;
                search(top, end);
            }
        }
    }
</script>

コメント

タイトルとURLをコピーしました