PHPの二分探索

二分探索とは何ですか?

二分探索は、ソートされた配列 (またはリスト) 内でターゲット値の位置を効率的に見つけるために使用される検索アルゴリズムです。これは、検索範囲を繰り返し半分に分割し、中央の要素をターゲット値と比較することによって機能します。

二分探索アルゴリズムは次の手順に従います。

• ソートされた配列全体から始めます。

• 左ポインタを配列の最初の要素に設定し、右ポインタを最後の要素に設定します。

• 中央のインデックスを左右のポインターの平均として計算します (整数除算)。

• 中間インデックスの値をターゲット値と比較します。

• 中間値がターゲット値と等しい場合、検索は成功し、アルゴリズムはインデックスを返します。

• ターゲット値が中央の値より大きい場合は、左ポインタを中央の 1 に更新して、検索範囲の左半分を削除します。

• ターゲット値が中央の値より小さい場合は、右ポインタをmid - 1に更新して、検索範囲の右半分を削除します。

• ターゲット値が見つかるか、検索範囲が空になるまで (左ポインタが右ポインタよりも大きくなるまで)、手順 3 ～ 7 を繰り返します。

• 検索範囲が空でターゲット値が見つからない場合、アルゴリズムはターゲット値が配列内に存在しないと判断し、-1 または適切な指示を返します。

二分探索は、時間計算量が O(log n) の非常に効率的なアルゴリズムです (n は配列内の要素の数です)。これは、各ステップで半分に分割することで検索範囲をすばやく絞り込み、多数の要素があっても高速な検索を可能にするため、大規模なソート済み配列の場合に特に効果的です。

二分探索 PHP プログラム

方法 1 - 反復を使用する

方法 2 - 再帰を使用する

要約すると、二分探索は、ソートされた配列内でターゲット値を効率的に見つけることができる強力なアルゴリズムです。これは、反復と再帰という 2 つの一般的な実装を提供します。反復法では、while ループを使用して、ターゲット値が見つかるか範囲が空になるまで、検索範囲を繰り返し半分に分割します。実装が簡単で、ほとんどのシナリオに最適です。一方、再帰的方法では、再帰関数を使用して二分検索を実行します。これは反復メソッドと同じロジックに従いますが、ループの代わりに関数呼び出しを使用します。再帰的バイナリ検索はよりクリーンな実装を提供しますが、関数呼び出しスタックの操作によりオーバーヘッドがわずかに高くなる可能性があります。全体として、どちらの方法もバイナリ検索操作を実行するための効率的で信頼性の高い方法を提供します。

以上がPHPの二分探索の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。