二分探索(バイナリサーチ)のアルゴリズム

このレッスンでは、二分探索というアルゴリズムを学び、並び替え済みのデータから効率よく目的の値を見つける方法を理解することを目標にします。「PHP 二分探索実装」で調べている方向けの内容です。

二分探索は、並び替え済みのデータから目的の値を効率よく探すアルゴリズムです。「辞書を開くとき、真ん中あたりから探して範囲を半分に絞っていく」ようなイメージです。先頭から1つずつ調べる方法に比べて、データ量が多いほど圧倒的に速く目的の値を見つけられます。

サンプルコードでは、$lowと$highという2つの添字で探索範囲を管理し、intdiv($low + $high, 2)で真ん中の位置を計算しています。intdiv()はPHPにおける整数の割り算専用の関数で、割り算の結果を整数に切り捨てて計算します。

初心者がよくつまずくのが、対象のデータがあらかじめ並び替えられている必要があるという前提条件です。並び替えられていない配列に対して二分探索を使っても正しい結果は得られません。事前のソートを忘れないようにしましょう。

データ構造とアルゴリズムの基礎として、就職試験のコーディングテストなどでもよく出題される定番の題材です。データ量が多いシステムでは、二分探索の高速さが特に大きな効果を発揮します。

📖 お手本コード

<?php
function binarySearch($arr, $target) {
    $low = 0;
    $high = count($arr) - 1;
    while ($low <= $high) {
        $mid = intdiv($low + $high, 2);
        if ($arr[$mid] === $target) return $mid;
        if ($arr[$mid] < $target) $low = $mid + 1;
        else $high = $mid - 1;
    }
    return -1;
}

$nums = [1, 3, 5, 7, 9, 11];
echo binarySearch($nums, 7) . "\n";
echo binarySearch($nums, 4);

✍️ あなたのコード

コードを書いたら「実行する」を押してください

🧪 このサイトではPHPを直接コンパイル・実行できないため、お手本コードと同じ内容を入力できたかをその場で判定します(採点はブラウザ内だけで行われ、どこにも送信されません)。

🎯

ここまでできればゴール達成!
大量のデータの中から目的の値を高速に見つけ出せるようになります。