PHP implements binary search algorithm (detailed code explanation)

Binary search is also called half search. The binary search algorithm requires that the data must be in order. The following is the code for implementing the binary search algorithm in PHP.

1: Recursive method

$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);

Execution results

int(0) int(25) int(13) int(25) int(20) int(25) int(20) int(21) bool(true)

We see that after 4 binary searches, the search interval is continuously cut in half, and finally found $target.

2: Loop method

$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);

Execution results

int(0) int(25) int(13) int(25) int(20) int(25) int(20) int(21) bool(true)

We see that the process and results of the two methods are the same. Let's test the binary search algorithm for associative arrays:

$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)

Two binary searches found $target. For associative arrays, we used PHP's array_keys function to obtain the key of this associative ordered array. Compare the values of $target and $array indirectly through key.

The above is the detailed content of PHP implements binary search algorithm (detailed code explanation). For more information, please follow other related articles on the PHP Chinese website!