Comment implémenter un algorithme de recherche binaire en utilisant PHP

Comment utiliser PHP pour implémenter un algorithme de recherche binaire

L'algorithme de recherche binaire est un algorithme de recherche efficace, adapté à la recherche d'éléments spécifiés dans des tableaux ordonnés. Cet article expliquera comment utiliser le langage PHP pour implémenter l'algorithme de recherche binaire et joindra des exemples de code.

L'idée de l'algorithme de recherche binaire est de diviser le tableau en deux parties, puis de déterminer dans quelle partie se trouve la valeur cible en comparant la relation de taille entre la valeur cible et l'élément du milieu. Si l'élément du milieu est égal à la valeur cible, la recherche réussit ; sinon, en fonction de la relation de taille entre l'élément du milieu et la valeur cible, continuez la recherche dans la partie correspondante jusqu'à ce que la valeur cible soit trouvée ou qu'il soit déterminé que l'élément du milieu est égal à la valeur cible. la valeur cible n’existe pas.

Ce qui suit est un exemple de code permettant à PHP d'implémenter l'algorithme de recherche binaire :

function binary_search($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    
    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);
        
        if ($arr[$mid] == $target) {
            return $mid;
        }
        
        if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    
    // 目标值不存在
    return -1;
}

$arr = [1, 3, 5, 7, 9, 11, 13, 15];
$target = 7;
$result = binary_search($arr, $target);

if ($result == -1) {
    echo "目标值不存在";
} else {
    echo "目标值在数组中的位置是：" . $result;
}

Exécutez le code ci-dessus, le résultat sera "La position de la valeur cible dans le tableau est : 3", indiquant que la position d'index de la valeur cible 7 dans le tableau est 3.

La fonction binary_search dans le code ci-dessus reçoit deux paramètres : le tableau ordonné à rechercher et la valeur cible. La fonction utilise deux pointeurs left et right pour représenter la plage de recherche du tableau. Réduisez continuellement la plage de recherche à travers la boucle while jusqu'à ce que la valeur cible soit trouvée ou qu'il soit déterminé que la valeur cible n'existe pas. binary_search函数接收两个参数：待查找的有序数组和目标值。函数使用两个指针left和right来表示数组的查找范围。通过while循环不断缩小查找范围，直到找到目标值或者确定目标值不存在。

代码中的关键是通过$mid

La clé du code est de calculer la position d'index de l'élément du milieu via la variable $mid, puis de la comparer avec la valeur cible. S'ils sont égaux, la position de l'index est renvoyée, sinon la plage de recherche est ajustée en fonction de la relation de taille et le prochain cycle de recherche binaire se poursuit.

Il convient de noter que l'algorithme de recherche binaire nécessite un tableau ordonné en entrée, sinon il ne peut pas être recherché correctement. Par conséquent, avant d'utiliser l'algorithme de recherche binaire, vous devez vous assurer que le tableau à rechercher a été trié par ordre croissant (ou décroissant).

La complexité temporelle de l'algorithme de recherche binaire est O(logn), ce qui est plus efficace que le O(n) de l'algorithme de recherche linéaire. Lors du traitement de données à grande échelle, l'utilisation de l'algorithme de recherche binaire peut améliorer considérablement l'efficacité de la recherche.

J'espère que cet article pourra aider les lecteurs à comprendre et à maîtriser la méthode d'utilisation du langage PHP pour implémenter l'algorithme de recherche binaire. En utilisant rationnellement l’algorithme de recherche binaire, nous pouvons effectuer plus efficacement les opérations de recherche dans des tableaux ordonnés. 🎜

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!