Am 14. September 2017 haben wir eine überarbeitete Fassung unserer Datenschutzrichtlinie veröffentlicht. Wenn Sie video2brain.com weiterhin nutzen, erklären Sie sich mit diesem überarbeiteten Dokument einverstanden. Bitte lesen Sie es deshalb sorgfältig durch.

Grundlagen der Programmierung: Datenstrukturen

Binäre Suche

LinkedIn Learning kostenlos und unverbindlich testen!

Jetzt testen Alle Abonnements anzeigen
Mit einer binären Suche kann wesentlich effizienter gesucht werden. Einzige Voraussetzung: Die Werte im Array müssen auf- bzw. absteigend sortiert sein.

Transkript

Lineare Suchmuster sind klar und gut verständlich. Sie sind einfach zu verfassen und sie sind langsam. Wenn allerdings die Werte in Ihrem Array auf- oder absteigend sind, können Sie es stattdessen mit einer binären Suche probieren. Es ist viel schneller und ich zeige Ihnen im Folgenden, wie sie funktioniert. Stellen Sie sich vor, wir haben ein Array mit Integer-Werten. Das können Zeichen sein, es könnte aber alles mögliche sein, Hauptsache, die Werte unterliegen einer auf- oder absteigenden Ordnung. Ich möchte wissen, ob der Wert 99 irgendwo im Array auftaucht. Nochmal: Mit einer linearen Suche müsste ich ausgehend vom ersten Element jedes Element untersuchen, bis ich zu meinem gewünschten Wert komme. Eine binäre Suche funktioniert anders. Sie beginnt nicht damit, beim ersten Element nachzuschauen, sondern damit, die Länge des Arrays herauszufinden. In unserem Fall sind es 22 Werte. Sie teilt dieses Array in zwei Bereiche und springt dann direkt an den erreichten Punkt in der Mitte des Arrays und vergleicht den Wert an dieser Position mit dem Wert, nach dem gesucht wird. In unserem Fall ist es die 99. Was wir hier finden, ist niedriger. Das bedeutet, dass, nachdem die Elemente geordnet sind, die eine Hälfte weggelegt werden kann und all die darin enthaltenen Elemente, da sie niedriger sind, nicht mehr relevant sind. Wir haben uns also in einem Schritt von der Hälfe des Arrays trennen können. Wir wissen, dass diese Werte sequentiell sind und dass daher der gesuchte Wert nicht in der niedrigeren Hälfte sein kann. Wir müssen uns diesen Teil nicht mehr anschauen. Wir machen also weiter. Wir nehmen den verbleibenden Teil, halbieren ihn neuerlich und springen zu diesem mittleren Punkt. Wir vergleichen den Wert dort mit dem gesuchten Wert. Würden wir hier nochmal teilen, kämen wir zum Wert 108. Der Wert 108 ist höher als 99. Das oder ein höheres Ergebnis ist also nicht das, was wir suchen. Wir können also auch 108 bis zum Ende einfach wegstreichen. Wir können jetzt die höhere Sektion ignorieren und beschäftigen uns nur noch mit einem Viertel. Wir fahren mit dem Halbieren fort, bis wir das gewünschte Ergebnis erreichen. Wir überprüfen das Ergebnis. Wir verwerfen die irrelevante Hälfte und machen weiter. Das nun ist die binäre Suche. Wobei binär hier nichts mit Nullen und Einsen zu tun hat, also mit Computercode. Binär heißt hier einfach zwei Teile. Wir teilen das Array immer wieder in zwei Teile. Dies wird auch als Halbintervallssuche bezeichnet oder allgemein als Divide-and-Conquer-Algorithmus, also als Teile-und-Herrsche-Algorithmus. Das ist eine unglaublich effiziente Art im Vergleich zur linearen Suche, vor allem, wenn es sich um große Arrays handelt. So können Sie sich mit einer Handvoll Abfragen durch große Arrays mit hunderten oder tausenden Elementen durcharbeiten. Das hört sich gut an. Also eine allgemein Frage: Wie kann ich eine binäre Suche in einem unsortierten Array ausführen? Die Antwort ist einfach. Es geht nicht. Ende der Geschichte. Binäre Suchen funktionieren nur bei geordneten Daten. Das ist die innewohnende Voraussetzung. Sie werden feststellen, dass die binäre Suche in fast jeder Programmiersprache zu finden ist. Java zum Beispiel bietet eine binäre Suchmethode in den Array-Werkzeugen an. .NET-Sprachen haben binäre Suchmethoden und Array-Klassen. C++ hat binary_search in seiner Standardbibliothek. Unglücklicherweise hat JavaScript keine eingebauten Binärsuchmethoden. Wir haben bsearch in Ruby und obwohl Objective C keine Methode mit dem Namen binäre Suche hat, unterstützt es binäre Suchen. Es gibt eine Version der indexOf-Methode, um etwas zu finden. Aber die Option taucht nur auf, wenn's um sortierte Daten geht. Bei einer sortierten Datenmenge wird dann einfach eine binäre Suche ausgeführt anstelle einer linearen Suche. Sie werden sich vorstellen können, wenn Sie ein Array befüllen, das aktuell nicht sortiert ist, dass Sie dann mit einem Error oder einem fehlenden Ergebnis rechnen müssen. Das ist das Wichtige an der Sache. Als ein pragmatischer, praktischer Softwareentwickler, oder als pragmatische, praktische Softwareentwicklerin wollen Sie keine binären Suchalgorithmen schreiben müssen. Vom Konzept her sind sie einfach. Aber es wäre ein Fehler, sie zu unterschätzen. Der Teufel liegt auch da im Detail. Drum ist es gut zu sehen, dass die Funktionalität in fast jeder Sprache implementiert ist. Sie sollten sie erkennen können, wenn Sie sie verwenden. Sie denken sich: Ich habe hier sortierte Daten und muss sie durchsuchen. Möglicherweise habe ich gerade ein klassisches indexOf-Statement geschrieben. Und ja, es wird funktionieren, aber lassen Sie uns einen Blick auf die Dokumentation Ihrer Sprache werfen und stellen Sie sicher, dass es nicht in einer ineffizienten linearen Suche enden wird, wenn es doch eine viel bessere Möglichkeit in der binären Suche gibt. Nochmal: Es ist eine leistungsschonende Suche. Soviel dazu. Obwohl binäre Suchen für sortierte Arrays großartig sind, findet man sie auch bei anderen Datenstrukturen wieder. weil sie eben gerade so eine praktische Form des Suchens darstellt.

Grundlagen der Programmierung: Datenstrukturen

Erhalten Sieeinen klaren Eindruck von Datenstrukturen und deren Eigenheiten und verstehen, wie Sie diese am besten einsetzen können – ganz unabhängig von den einzelnen Programmiersprachen.

2 Std. 51 min (29 Videos)
Derzeit sind keine Feedbacks vorhanden...
 

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!