PHP implémente un algorithme de recherche binaire (explication détaillée du code)-tutoriel php-php.cn

PHP implémente un algorithme de recherche binaire (explication détaillée du code)

藏色散人

Libérer： 2023-04-06 13:16:01

avant

8110 Les gens l'ont consulté

La recherche binaire est également appelée demi-recherche. L'algorithme de recherche binaire nécessite que les données soient dans l'ordre. Voici le code d'implémentation de l'algorithme de recherche binaire en PHP.

1 : Méthode récursive

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

Copier après la connexion

Résultats d'exécution

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

Copier après la connexion

On voit qu'après 4 recherches binaires, l'intervalle de recherche est continuellement réduit de moitié, et finalement trouvé $cible.

Deux : Méthode de boucle

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

Copier après la connexion

Résultat de l'exécution

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

Copier après la connexion

Nous voyons que le processus et les résultats des deux méthodes sont les mêmes. Testons l'algorithme de recherche binaire pour les tableaux associatifs :

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

Copier après la connexion

Deux recherches binaires ont trouvé $target. Pour les tableaux associatifs, nous avons utilisé la fonction array_keys de PHP pour obtenir la clé de ce tableau ordonné associatif. target et $array indirectement via la clé.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!