PHPで二分探索

ソート済み配列から目的の値を効率よく探す、二分探索（バイナリサーチ）の実装例です。コピペで動くコードと実行結果、処理の流れを確認できます。 下のコードはブラウザ内でそのまま実行できます。「実行エディタで開く」を押すと、progoのオンラインPHP実行環境にコードが読み込まれ、その場で動作を確認できます。

サンプルコード

$arr = [1, 3, 5, 7, 9, 11, 13];
$target = 9;
$low = 0;
$high = count($arr) - 1;
$result = -1;
while ($low <= $high) {
    $mid = intdiv($low + $high, 2);
    if ($arr[$mid] == $target) {
        $result = $mid;
        break;
    } elseif ($arr[$mid] < $target) {
        $low = $mid + 1;
    } else {
        $high = $mid - 1;
    }
}
echo "インデックス: " . $result . "\n";

ポイント解説

• 対象配列はあらかじめソートされている必要があります。
• 中央値と比較して探索範囲を半分に絞ります。
• 計算量はO(log n)と高速です。