Suchalgorithmen

Binäre Suche in PHP verstehen

Die binäre Suche ist ein effizienterer Algorithmus zum Suchen eines Elements in einem sortierten Array. Es funktioniert durch wiederholtes Teilen des Suchintervalls in zwei Hälften. Hier ist eine detaillierte Aufschlüsselung Ihrer binären Suchfunktion:

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)

Die Funktion „binarySearch“ akzeptiert zwei Parameter:

1. $arr: Ein sortiertes Array von Ganzzahlen.
2. $x: Die zu suchende Zahl, die eine Gleitkommazahl oder eine Ganzzahl sein kann.
3. $low wird auf den ersten Index des Arrays initialisiert.
4. $high wird auf den letzten Index des Arrays initialisiert.
5. $i ist ein Zähler, um die Anzahl der Iterationen zu verfolgen.
6. Die while-Schleife läuft, solange das Suchintervall gültig ist ($low ist kleiner oder gleich $high).
7. $midIndex wird als mittlerer Index des aktuellen Intervalls berechnet.
8. Wenn das mittlere Element gleich $x ist, gibt die Funktion den Index und die Anzahl der Iterationen zurück.
9. Wenn $x größer als das mittlere Element ist, passen Sie $low auf midIndex + 1 an (schränken Sie die Suche auf die obere Hälfte ein).
10. Wenn $x kleiner als das mittlere Element ist, passen Sie $high auf midIndex - 1 an (schränken Sie die Suche auf die untere Hälfte ein).

Grundlegendes zur linearen Suche in PHP

Die lineare Suche ist einer der einfachsten Suchalgorithmen, der zum Auffinden eines bestimmten Elements in einem Array verwendet wird. Lassen Sie uns die linearSearch-Funktion in PHP aufschlüsseln.

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

Die Funktion linearSearch akzeptiert zwei Parameter:

1. $arr: Ein Array von Ganzzahlen.
2. $x: Die zu suchende Zahl, die eine Gleitkommazahl oder eine Ganzzahl sein kann.
3. Die for-Schleife durchläuft jedes Element des Arrays. Die Funktion count($arr) gibt die Anzahl der Elemente im Array zurück.
4. Innerhalb der Schleife prüft der Code, ob das aktuelle Element ($arr[$i]) gleich $x ist. Wenn eine Übereinstimmung gefunden wird, wird eine Meldung zurückgegeben, die den Index angibt, an dem die Nummer gefunden wurde.
5. Wenn die Schleife abgeschlossen wird, ohne dass die Nummer gefunden wird, gibt die Funktion eine Meldung zurück, die angibt, dass die Nummer nicht im Array gefunden wurde.
6. Die lineare Suche ist unkompliziert und einfach zu implementieren. Es überprüft nacheinander jedes Element des Arrays, bis das gewünschte Element gefunden oder das Ende des Arrays erreicht ist. Dieser Ansatz ist einfach, kann aber für große Arrays ineffizient sein, da er eine zeitliche Komplexität von O(n) hat.

Das obige ist der detaillierte Inhalt vonSuchalgorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!