close

(Binary Search) PHP の 二分探索アルゴリズム: 説明、手順、および例

二分探索アルゴリズムは、並べ替えられた配列内の特定の値を見つけるための効率的な方法です。 この手法では、配列をより小さな部分に分割し、検索範囲の中間位置の値とターゲット値を継続的に比較します。 値が一致すると、目的の値が見つかります。 それ以外の場合、アルゴリズムは引き続き検索範囲を絞り込み、値が見つかるか調べる要素がなくなるまでプロセスを繰り返します。

手順:

  1. 検索範囲の初期化: まず、 配列の最初の位置から left  最後の位置までの 検索範囲を選択します。 right
  2. 中間点を見つける: と右側の位置を平均して中間点を計算します left。 これは検索範囲の中点です。
  3. 値を比較: 中点の値と目標値を比較します。
  4. ハンドル比較結果： 中点の値が目標値と一致した場合、その位置を返します。 中点の値が目標値より小さい場合は、左の位置を中+1に更新して右半分を検索します。 中点の値が目標値より大きい場合は、右位置を中央- 1 に更新して左半分を検索します。
  5. 繰り返し: 値が見つかるか、チェックする要素がなくなるまで、手順 2 ～ 4 を繰り返します left > right。

長所と短所

利点:

  • 効率的なパフォーマンス: アルゴリズムの時間計算量は O(log n) であり、大規模なデータセットを処理する場合に非常に効率的です。
  • 大規模なデータセットに効果的: 二分探索は、大規模なデータセットを迅速に調べる要素の数を減らすのに効果的です。

短所:

  • ソートされた配列にのみ適用可能: アルゴリズムはソートされた配列でのみ機能します。
  • 可変ステップ数: 値を見つけるのに必要なステップ数は、配列内の値の位置によって異なり、末尾に近い値の場合は多くのステップが必要となる場合があります。

例: PHP でソートされた配列内の値 12 を見つけるための二分探索 

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}

例の説明

  1.  配列の最初の位置から left = 0 最後の位置までの 初期検索範囲から始めます。 right = 6
  2. 左右の位置を平均して中間点(mid) を計算します。 mid = 3。 中間の値は 12 です。
  3. )の値 mid(12 とターゲット値(12) を比較し、一致するものが見つかったので、位置 3 を返します。
  4. アルゴリズムが終了し、「位置 3 で値 12 が見つかりました」という結果が出力されます。