#41 二分探索を可視化してみた

概要

普段よく探索アルゴリズムを使っているので動きを理解するために二分探索を実装して可視化してみたいと思います

この記事は前回のクイックソートをCanvasを用いて可視化してみたの関連記事となります

二分探索の実装

二分探索の概要

二分探索とは、ソートされた配列に適用できる探索アルゴリズムで、検索対象の値が配列の中央の値より大きいか小さいかを繰り返し判断して範囲を絞り込んでいく手法です

前提条件: 検索したい配列がソートされていること

1. 検索したい値と配列の中央値を比較して値が同じ値であれば探索を終了し、そうでないのならば2へ進みます
2. 検索したい値が大きい場合は検索する配列の範囲を配列の後半に、小さい場合は配列の前半を探索する配列の範囲とし、1に戻ります

実装

TypeScriptでソート関数を以下のように実装しました。

• array T[] 探索対象の配列
• compareFunction: (a: T, b: T) => boolean 比較用の関数
• option
  • start?: number 探索対象の範囲の先頭のインデックス
  • end?: number 探索対象の範囲の最後尾のインデックス
  • fn? 毎ステップ呼ばれる関数。今回も視覚化のために使います

/**
 * 
 * @param array ソート対象の配列
 * @param target 検索したい値
 * @param compareFunction 比較関数(昇順でソートされている場合: t - a)
 * @param option ソートの範囲やステップごとに呼ばれる関数など
 * @returns 
 */
async function binarySearch<T, U>(
    array: T[],
    target: U,
    compareFunction: (a: T, t: U) => number,
    option?: {
        start?: number,
        end?: number,
        fn?: (
            array: T[],
            i: U,
            start: number,
            end: number
        ) => Promise<void>
    }) {
    //ソート対象の範囲
    const start = (option?.start != undefined) ? option.start : 0;
    const end = (option?.end != undefined) ? option.end : array.length;

    let index = Math.floor((end + start) / 2);

    //オプションで関数が与えられていた場合呼び出す
    if (option?.fn) await option.fn(array, target, start, end);

    //もし、検索対象の位置を特定出来たら位置を返す
    if (compareFunction(array[index], target) == 0) {
        return index;
    }
    //もし、検索対象が探索範囲の中央の値より小さいなら探索対象を前半に絞り込む
    if (compareFunction(array[index], target) < 0) {
        return await binarySearch(array, target, compareFunction, { start: start, end: index, fn: option?.fn });
    }
    //もし、検索対象が探索範囲の中央の値より大きいなら探索対象を後半に絞り込む
    if (compareFunction(array[index], target) > 0) {
        return await binarySearch(array, target, compareFunction, { start: index, end: end, fn: option?.fn });
    }
}

実際に動かしてみる

実装

• const index = binarySearch(array, target, (a, t) => { return t - a }, { fn: draw });
  • 二分探索を行い、検索対象の位置を返します

他の関数などに関しては前回の記事を参照してください

async function main() {
    //配列の初期化
    let array: number[] = new Array();
    let target = 0;
    for (let i = 0; i < 1000; i++) {
        target = Math.floor(Math.random() * 1000000)
        array.push(target);
    }

    const g = new Graph('graph', 1000000);

    async function draw(a: number[], target: number, start: number, end: number) {
        const data: { value: number, color: string, }[] = new Array();
        for (let i = 0; i < a.length; i++) {
            if (a[i] == target) {
                data.push({ value: a[i], color: "green" });
            }
            else if (start <= i && i <= end) {
                data.push({ value: a[i], color: "lightblue" });
            }
            else {
                data.push({ value: a[i], color: "gray" });
            }
        }
        await wait(1000);
        g.setData(data);
        g.draw();

        return;
    }

    //ソート
    array = await qsort(array, (a, b) => { return a < b });

    const index = binarySearch(array, target, (a, t) => { return t - a }, { fn: draw });
    console.log(`${target} index: ${index}`);
}

main();

コンパイルして実行確認

TypeScriptはブラウザ上では動作しないので今回もtscコマンドでコンパイルします

$ tsc ./src/main.ts

前回と同じようにhtmlファイルをブラウザで開くと、探索範囲を繰り返し半分にする様子が視覚化できました

See the Pen Untitled by mm (@NXTEDmm) on CodePen.

まとめ

今回は二分探索を視覚化してみました。

配列を繰り返し分割して処理していく様子はクイックソートにも似ていることがわかりました。

※二分探索やクイックソートのように対象を繰り返し分割して結果を求める手法のことを分割統治法といいます。

この記事が参考になれば幸いです。最後までご覧いただきありがとうございました