日本語
日本語
バイナリ検索としても知られるPHPのハーフファインディング検索アルゴリズムは、順序付けられた配列で要素位置を効率的に見つけるために使用される古典的なアルゴリズムです。検索範囲を常に半分に分割し、ターゲット要素と中間要素とのサイズの関係を判断することにより、ターゲットが存在しないと判断されるまで、検索範囲をすぐに絞り込みます。
折りたたみ式のハーフルックアップのコアステップは次のとおりです。
配列の開始インデックスを左に設定し、端インデックスを右に設定します。
中間インデックスミッド、つまり（左 +右） / 2を計算します。
ターゲット値を中間要素と比較します。等しい場合は、インデックスの中間を返し、検索が成功します。
ターゲット値が中間要素よりも小さい場合は、右から1 -1を右に設定し、左半分で検索し続けます。
ターゲット値が中間要素よりも大きい場合は、左+ 1に左に設定し、右半分で検索し続けます。
ターゲット値または左>右が見つかるまで上記の手順を繰り返し、検索が失敗したことを示します。
以下は、ハーフファインディング検索アルゴリズムの実装を実証するためのPHPコードの例です。
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr) - 1;
while ($left <= $right) {
$mid = intval(($left + $right) / 2);
if ($arr[$mid] == $target) {
return $mid; // 目標値の位置
}
if ($arr[$mid] < $target) {
$left = $mid + 1; // 右半分で検索を続けます
} else {
$right = $mid - 1; // 左半分を検索し続けます
}
}
return -1; // 目標値は見つかりませんでした
}
<p>$arr = [1, 3, 5, 7, 9, 11, 15];<br>
$target = 7;<br>
$index = binarySearch($arr, $target);<br>
if ($index != -1) {<br>
echo "目標値 $target 配列の位置はです $index";<br>
} else {<br>
echo "目標値 $target 配列には存在しません";<br>
}<br>
上記のコードは、順序付けられた配列とターゲット値をパラメーターとして受け入れるバイナリセア機能を定義し、配列のターゲット値のインデックス位置を返し、存在しない場合は-1を返します。
ハーフファインディング検索アルゴリズムの時間の複雑さはO（log n）で、 nは配列長です。各ルックアップは範囲を半分に減らします。これは、線形ルックアップよりもはるかに効率的です。
したがって、バイナリ検索は、大規模な順序付けられたアレイの高速位置決め要素に非常に適しています。
バイナリ検索は、検索範囲を大幅に狭め、比較の数を減らし、特に大量のデータ量を使用したシナリオに適した高速位置を達成することができます。
頻繁な検索操作を備えたアプリケーションでは、バイナリ検索を使用すると、時間オーバーヘッドを大幅に短縮し、全体的な実行効率を改善し、不必要なトラバーサルを回避できます。
この記事では、PHP Mid倍半フィニッシュ（バイナリ検索）アルゴリズムの原則と実装を体系的に説明し、コードの例を介した特定の使用法を示しています。このアルゴリズムには、低時間の複雑さと高効率の特性があり、順序付けられた配列の効率的な検索に適しています。このアルゴリズムを習得すると、問題発見とプログラムのパフォーマンスに対処する開発者の能力が向上します。
