Binäre Suche mit PHP

Ich bin grade dabei mich auf die mündliche Nachprüfung zu Algorithmen vorzubereiten. Aus diesem Grund hab ich mir das Ziel Gesetzt möglichst alle Algorithmen die wir da hatten auch mal in PHP zu programmieren. Den Anfang macht die Suche.

Bei der ganz normalen linearen Suche wird die Liste oder hier der Array ja einfach von einer Seite her durch gegangen bis der gesuchte Wert gefunden wurde.
Das sieht dann so aus:

function linear_search($a, $k){
    for($i = 0; $i < count($a); $i++){
        if($k == $a[$i]){
            return true;
        }
    }
    return false;
}

Joa, da ist ja nix weiter dabei. Die Binäre Suche sieht dann schon bissl komplizierter aus:

function binary_search($a, $k){

    //Mitte finden
    $mitte = round(count($a)/2, 0)-1;

    //wenn die Mitte der gesuchte Wert ist...
    if($k == $a[$mitte]){
        echo $a[$mitte]." gefunden";
        return true;
    }
    //wenn der Array nur noch einen Wert enthält aber die Mitte nicht
    //der gesuchte Wert ist
    elseif(count($a)==1){
        echo $k." nicht gefunden";
        return false;
    }
    //wenn der gesuchte Wert kleiner als die Mitte ist...
    elseif($k < $a[$mitte]) {
        //Array aus linker Hälfte bilden und in dieser weitersuchen
        return binary_search(array_slice($a, 0, $mitte), $k);
    }
    //wenn der gesuchte Wert größer als die Mitte ist...
    elseif($k > $a[$mitte-1]) {
        //Array aus rechter Hälfte bilden und in dieser weitersuchen
        return binary_search(array_slice($a, $mitte+1, count($a)), $k);
    }
}

Ja, vielleicht kanns ja mal wer brauchen! 😉

PS: Irgendwie sieht das so hier mächtig scheiße aus. Leider hab ich kein gescheites Plugin für WordPress gefunden dass vielleicht sogar sowas wie Syntax Highlighting für PHP kann, geschweige denn überhaupt eines welches die Code-Funktion hier etwas aufmöbelt!

Edit:
Mit der richtigen Suchzeile findet man auch das passende Ergebnis! 🙂 Bei meinem “Hinundwieder-Arbeitgeber” der ilimitado OHG aus Tübingen hab ich ein wp-syntax gefunden. Dieses Plug-In beherrscht sogar Syntax-Highlighting und kann über 80 Sprachen! So sieht das doch schon deutlich besser aus!

3 thoughts to “Binäre Suche mit PHP”

  1. Deine Lineare Suche müsste eigentlich einen Array out of Bounds Fehler schmeißen. Wenn du bei 0 anfängst zu zählen, darfst du nur $i

  2. Hallo!

    …darf ich nur? Da fehlt der Rest vom Satz, oder?
    Auf jeden Fall hats funktioniert.

    Aber du hast vielleicht gemeint, dass $i nur bis count($a)-1 gehen darf. Darum sieht die for-Schleife jetzt so aus:

    for($i = 0; $i < count($a); $i++){
    

    und nicht mehr so:

    for($i = 0; $i < = count($a); $i++){
    

    Funktioniert auch und ist wohl theoretisch richtiger. Wobei das was ich davor hatte eigentlich schon nen Fehler ausgeben hätte müssen wenn ein Wert gesucht wird der nicht im Array ist. Tjo... wieso hat das trotzdem funktioniert?

  3. Jo, der halbe satz fehlt.
    Wenn du count zählt ja von 1 ab. Also bei 8 elementen ist count = 8, ein array geht aber bei 0 los, d.h. das letzte Element ist das Element array[7], wenn deine schleife nun bis array[8] geht, sollte es einen Fehler geben. PHP ist je nach einstellung nicht wirklich safe. Hier ist wohl einfach das letzte Element NULL.
    Bei anderen Sprachen, wo Arrays meist fix angelegt sind, würde dieses nicht abfangen dazu führen, dass man irgendeinen müll, welcher zufällig nach dem Array liegt, verarbeiten würde. Und das macht man natürlich nicht.
    PHP schützt einen halt vor sich selbst. Jedenfalls ist die Schleife so wie du sie jetzt hast, nicht nur theoretisch richtig, sondern auch praktisch richtig 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *