PHP implements binary search algorithm (detailed code explanation)-PHP Tutorial-php.cn

PHP implements binary search algorithm (detailed code explanation)

藏色散人

Release： 2023-04-06 13:16:01

forward

8067 people have browsed it

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

Copy after login

Execution results

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

Copy after login

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

Copy after login

Execution results

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

Copy after login

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 = [&#39;a&#39;=>1,&#39;b&#39;=>3,&#39;c&#39;=>6,&#39;d&#39;=>9,&#39;e&#39;=>13,&#39;f&#39;=>18,&#39;g&#39;=>19,&#39;h&#39;=>29,&#39;i&#39;=>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)

Copy after login

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!