二分探索は半探索とも呼ばれます。二分探索アルゴリズムでは、データが順序どおりである必要があります。以下は、PHP で二分探索アルゴリズムを実装するコードです。
1: 再帰的手法
$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89]; $target = 73; $low = 0; $high = count($array)-1; function bin_search($array, $low, $high, $target){ if ( $low <= $high){ var_dump($low, $high);echo "\n"; $mid = intval(($low+$high)/2 ); if ($array[$mid] == $target){ return true; }elseif ( $target < $array[$mid]){ return bin_search($array, $low, $mid-1, $target); }else{ return bin_search($array, $mid+ 1, $high, $target); } } return false; } $find = bin_search($array, $low, $high, $target); var_dump($find);
実行結果
int(0) int(25) int(13) int(25) int(20) int(25) int(20) int(21) bool(true)
4 回のバイナリ検索の後、検索間隔が継続的に半分になることがわかります。ついに $target を見つけました。
2: ループメソッド
$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89]; $target = 73; function bin_search($array, $target) { $low = 0; $high = count($array)-1; $find = false; while (true){ if ($low <= $high){ var_dump($low, $high);echo "\n"; $mid = intval(($low + $high)/2); if ($array[$mid] == $target){ $find = true; break; } elseif ($array[$mid] < $target){ $low = $mid+1; } elseif ($array[$mid] > $target){ $high = $mid-1; } } else { break; } } return $find; } $find = bin_search($array, $target); var_dump($find);
実行結果
int(0) int(25) int(13) int(25) int(20) int(25) int(20) int(21) bool(true)
2 つのメソッドのプロセスと結果は同じであることがわかります。連想配列の二分検索アルゴリズムをテストしてみましょう:
$array = ['a'=>1,'b'=>3,'c'=>6,'d'=>9,'e'=>13,'f'=>18,'g'=>19,'h'=>29,'i'=>38]; $target = 19; function bin_search($array, $target) { $low = 0; $high = count($array)-1; $key_map = array_keys($array); $find = false; while (true){ if ($low <= $high){ var_dump($low, $high);echo "\n"; $mid = intval(($low + $high)/2); if ($array[$key_map[$mid]] == $target){ $find = true; break; } elseif ($array[$key_map[$mid]] < $target){ $low = $mid+1; } elseif ($array[$key_map[$mid]] > $target){ $high = $mid-1; } } else { break; } } return $find; } $find = bin_search($array, $target); var_dump($find); 执行结果 int(0) int(8) int(5) int(8) bool(true)
2 つの二分検索で $target が見つかりました。連想配列の場合、PHP の array_keys 関数を使用して、この連想配列のキーを取得しました。$ の値を比較します。 target と $array はキーを介して間接的に取得されます。
以上がPHP は二分探索アルゴリズムを実装します (詳細なコードの説明)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。