Algorithmes de recherche

Comprendre la recherche binaire en PHP

La recherche binaire est un algorithme plus efficace pour trouver un élément dans un tableau trié. Cela fonctionne en divisant à plusieurs reprises l’intervalle de recherche en deux. Voici une description détaillée de votre fonction binaireSearch :

function binarySearch(array $arr, float|int $x)
{
    $low = 0;
    $high = count($arr)-1;
    // $midIndex = (int) ($low + ($high - $low)/2);
    $i = 0;
    while($low <= $high){
        $i++;
        $midIndex = (int) ($low + (($high - $low)/2)); //the same as  intdiv($low + $high, 2);

        if($arr[$midIndex] == $x){
            return "The number {$x} was found in index {$midIndex} of the array. The number of iteration was {$i}";
        }elseif($x > $arr[$midIndex]){
            $low = $midIndex +1;
            echo $low."\n";
        }else{
            $high = $midIndex - 1;
        }
    }

return "The number {$x} was not found in the array";


}

echo binarySearch([1,2,3,4,5,6,7,8,9,10,44,45,46,47,48,49,50], 45)

La fonction binaireSearch accepte deux paramètres :

1. $arr : Un tableau trié d'entiers.
2. $x : Le nombre à rechercher, qui peut être un flottant ou un entier.
3. $low est initialisé au premier index du tableau.
4. $high est initialisé au dernier index du tableau.
5. $i est un compteur pour garder une trace du nombre d'itérations.
6. La boucle while s'exécute tant que l'intervalle de recherche est valide ($low est inférieur ou égal à $high).
7. $midIndex est calculé comme l'indice médian de l'intervalle actuel.
8. Si l'élément du milieu est égal à $x, la fonction renvoie l'index et le nombre d'itérations.
9. Si $x est supérieur à l'élément du milieu, ajustez $low à midIndex + 1 (limitez la recherche à la moitié supérieure).
10. Si $x est inférieur à l'élément du milieu, ajustez $high à midIndex - 1 (limitez la recherche à la moitié inférieure).

Comprendre la recherche linéaire en PHP

La recherche linéaire est l'un des algorithmes de recherche les plus simples utilisés pour trouver un élément particulier dans un tableau. Décomposons la fonction LinearSearch en PHP.

function linearSearch(array $arr, float|int $x)
{
    for($i=0; $i < count($arr); $i++){
        if($x === $arr[$i]){
            return "The number {$x} was found in index {$i} of the array\n";
        }
    }

    return "The number {$x} was not found in the array\n";
}

echo linearSearch([1,5,6,3,4,11,3,2], 4);

La fonction LinearSearch accepte deux paramètres :

1. $arr : Un tableau d'entiers.
2. $x : Le nombre à rechercher, qui peut être un flottant ou un entier.
3. La boucle for parcourt chaque élément du tableau. La fonction count ($ arr) renvoie le nombre d'éléments dans le tableau.
4. A l'intérieur de la boucle, le code vérifie si l'élément courant ($arr[$i]) est égal à $x. Si une correspondance est trouvée, il renvoie un message indiquant l'index auquel le numéro a été trouvé.
5. Si la boucle se termine sans trouver le numéro, la fonction renvoie un message indiquant que le numéro n'a pas été trouvé dans le tableau.
6. La recherche linéaire est simple et facile à mettre en œuvre. Il vérifie séquentiellement chaque élément du tableau jusqu'à ce que l'élément souhaité soit trouvé ou que la fin du tableau soit atteinte. Cette approche est simple mais peut s'avérer inefficace pour les grands tableaux, car elle a une complexité temporelle de O(n).

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!