株式会社I-SEED(アイシード)|大阪・心斎橋のWEB制作集団

【アルゴリズム】配列内を早く検索する!【二分探索】

【アルゴリズム】配列内を早く検索する!【二分探索】

全力疾走熱中症全力疾走熱中症
この記事は、2020年1月27日に編集し、約 6 分で読めます。

今回は配列内を検索する手段として二分探索という方法を紹介したいと思います。

状況は限られていますが、適用できれば非常に強力な方法です。

二分探索

図とコード(PHP)を使って解説していきます

図解

例えば以下のような配列が存在し、数値の21を探したいとします。
※配列の中はあらかじめソートされていると前提します。

上記の配列から特定の数字を探す場合、どういった方法が良いのでしょうか?

通常探索

まず順番に探していく場合、下記のとおりになります。

ご覧の通り、順番に探していく場合はかなり手間になります。

二分探索

二分探索の場合はどうでしょうか。

まず配列の真ん中にある数値を探索します。
今回だと「(0 + 10) / 2 = 5」になるので配列の真ん中は[5]であることが分かります。

配列[5]の中には数値15が入っています。探したい数値は21なのでまだ正解にはたどり着いていません。
しかし、配列[5]以降に探している数値21はあることが分かりました。

次は配列[6]から[10]の真ん中を見に行きます。
「(6 + 10) / 2 = 8」になるので次は配列[8]の値をチェックします。

すると、配列[8]の中身は21ですね。これで正解の数値にたどり着きました。

このように探索する回数を減らして目的の数値を探せる方法が「二分探索」です。

コード

では次はコードと簡単な処理時間を比較してみたいと思います。コードはPHPで記載されています。
数値が1-100000まで入った配列からランダムに数値を探索するという内容を1000回ループさせて実行時間を計測します。

通常の場合(for文)

まずは配列の最初から探索していく方法を試してみたいと思います。
for文で実行します。

<?php
// 配列作成
$test_list = range(1, 100000);

// 計測開始
$start_time = microtime(true);

// 1000回繰り返し
for ($count = 0; $count < 1000; $count++) {
    // 探す数値を決定
    $search_num = rand(1, 100000);

    // 数値を探す
    for ($i = 0; $i < count($test_list); $i++) {
        if ($search_num === $test_list[$i]) {
            echo $search_num . '->' . $test_list[$i] . PHP_EOL;
            break;
        }
    }
}

// 計測終了
$end_time = microtime(true);

// 経過時間
$time = $end_time - $start_time;
echo '平均:' . ($time / 1000) . '秒' . PHP_EOL; //平均:0.00093360686302185秒
echo '合計:' . $time . '秒' . PHP_EOL; //合計:0.93360686302185秒

上記の結果でした。for文以外は果たしてどうなるでしょうか。

PHPの場合(array_search()関数)

PHPには指定した値を配列で検索し、見つかった場合に対応する最初のキーを返すarray_search()関数が存在します。
次はその関数で実行してみたいと思います。

<?php
// 配列作成
$test_list = range(1, 100000);

// 計測開始
$start_time = microtime(true);

// 1000回繰り返し
for ($count = 0; $count < 1000; $count++) {
    // 探す数値を決定
    $search_num = rand(1, 100000);

    // 数値を探す
    for ($i = 0; $i < count($test_list); $i++) {
        $res = array_search($search_num, $test_list, true);
        if ($res) {
            echo $search_num . '->' . $test_list[$i] . PHP_EOL;
            break;
        }
    }
}

// 計測終了
$end_time = microtime(true);

// 経過時間
$time = $end_time - $start_time;
echo '平均:' . ($time / 1000) . '秒' . PHP_EOL; //平均:0.00015707898139954秒
echo '合計:' . $time . '秒' . PHP_EOL; //合計:0.15707898139954秒

for文より早いですね、二分探索はどうなるのでしょうか。

二分探索の場合

最後に、二分探索で実行してみたいと思います。

<?php
// 配列作成
$test_list = range(1, 100000);

// 計測開始
$start_time = microtime(true);

// 1000回繰り返し
for ($count = 0; $count < 1000; $count++) {
    // 探す数値を決定
    $search_num = rand(1, 100000);

    // 数値を探す
    $start = 0;
    $end = count($test_list) - 1;
    while ($start <= $end) {
        $middle = (int)(($start + $end) / 2);
        if ($test_list[$middle] === $search_num) {
            echo $search_num . '->' . $test_list[$middle] . PHP_EOL;
            break;
        } elseif ($test_list[$middle] < $search_num) {
            $start = $middle + 1;
        } else {
            $end = $middle - 1;
        }
    }
}

// 計測終了
$end_time = microtime(true);

// 経過時間
$time = $end_time - $start_time;
echo '平均:' . ($time / 1000) . '秒' . PHP_EOL; //2.7949810028076E-6秒
echo '合計:' . $time . '秒' . PHP_EOL; //0.0027949810028076秒

for文やarray_search()関数より圧倒的に早いという結果になりました。

まとめ

このように二分探索は特定の条件下で配列内を高速に探索することが可能な手法です。

もし競技プログラミング等に参加している方はよく使うのでぜひ覚えておきたいですね。

最後まで読んでいただき、ありがとうございました。

この記事を書いた人
全力疾走熱中症

好きな言葉「休憩」, 全然できないこと「PHP」

全力疾走熱中症をフォローする

WEBの事でお悩みなら、まずは一度 I-SEED にご相談ください!

I-SEED は 「デザイン」「SEOマーケティング」「システム開発」を併せ持つWEB制作会社です。

コーポレート、オウンドメディア、ECなど様々な分野のサイト制作を得意としています。システム開発も自社で行っているので、様々なプロジェクトに柔軟かつ迅速に対応できるのが強みです。

大阪に良いWEB制作会社がいないとお困りの方は、是非一度 I-SEED までご相談ください。

I-SEED では随時採用も行っています。各種エンジニア、ディレクター、デザイナー、ライター、マーケターの全職種を募集しています。ご興味がある方は採用ページもご覧ください。

ブログページに戻る