Mathematik-Grundbegriffe für Programmierer

Suchalgorithmen und deren Effizienz

LinkedIn Learning kostenlos und unverbindlich testen!

Jetzt testen Alle Abonnements anzeigen
In der Programmierpraxis wird häufig in Datenstrukturen (etwa einem Array) ein Element mit bestimmten Eigenschaften gesucht. Dazu gibt es verschiedene Suchalgorithmen, die sich bezüglich Aufbau und Effizienz unterscheiden. Bei Suchalgorithmen wird die Effizienz an der Anzahl der Vergleiche gemessen, die zur Lösung notwendig sind. Das Video zeigt konkret die (einfache) lineare Suche und die binäre Suche.
06:16

Transkript

In der Programmierung wird häufig in einer Datenstruktur, beispielsweise einem Array, nach einem bestimmten Element gesucht, es hat bestimmte Eigenschaften. Es gibt verschiedene Suchalgorithmen, die sich bezüglich des Aufbaus und der Effizienz unterscheiden. Dabei wird die Effizienz durch die Anzahl der Vergleiche gemessen, die zur Lösung einer Suche notwendig sind. In diesem Video wollen wir uns zwei Suchalgorithmen vornehmen; das ist einmal die einfache lineare Suche und die binäre Suche. Ich habe hier ein Beispiel-Programm für die lineare Suche vorbereitet. Bei der linearen Suche wird eine Menge an Elementen, beispielsweise ein Array, nach einem bestimmten Kriterium durchsucht, zum Beispiel dem Minimum oder Maximum der Werte. Eine solche lineare Suche ist sehr langsam, da jedes Element des Arrays verglichen werden muss. Bei einer linearen Suche steigt die Anzahl der Vergleiche linear mit der Anzahl der Elemente. Schauen wir uns das mal hier an. Ich habe hier ein eindimensionales Array mit Namen "Zahl" und ich möchte hier das Maximum bestimmen. Das heißt, ich habe hier eine Schleife, die über das komplette Array iteriert und jeden einzelnen Eintrag in diesem Array mit dem bisher gefundenen Maximum vergleicht. Ich lasse das Beispiel mal laufen. "Menuleiste RUN RUN" Und Sie bekommen für dieses konkrete Beispiel den Index des Maximums; das ist hier die 99. Das fünfte Element, 0, indiziert das Array, also kommt der Wert 4. Die sogenannte binäre Suche ist erheblich effektiver als die lineare Suche, sie ist viel schneller, aber sie setzt voraus, dass eine Datenstruktur sortiert vorliegt. Die Anzahl der Vergleiche bei der binären Suche steigt logarithmisch an. Das zeigt deutlich, dass es viel,viel effizienter ist. Ich habe hier ein Beispiel für eine binäre Suche. Sie funktioniert nach folgendem Prinzip: Es wird zuerst das mittlere Element in der sortierten Datenmenge untersucht. Ist es größer als ein gesuchtes Element, muss nur noch in der linken Hälfte gesucht werden. Im anderen Fall sucht man in der rechten Hälfte. Nun wird die Suche auf die neue Datenmenge angewendet und auch da halbiert man die Datenmenge. Das mittlere Element der halbierten Menge wird mit dem gesuchten Element verglichen. Ist das mittlere Element größer, wird in der unteren Hälfte weitergesucht, ansonsten in der oberen Hälfte. Sie sehen also, dass sich bei jeden Schritt des Algorithmus die Anzahl der Elemente halbiert, die noch untersucht werden müssen. Dieses Beispiel hier demonstriert das. Ich habe dazu links und rechts als Variablen definiert und eine Variable für die Mitte. Dazu eine Boolean-Variable, die anzeigt, ob ein Element gefunden wurde oder nicht. Und Sie sehen, dass in der Schleife das mittlere Element bestimmt wird. Das sind die Werte von links und rechts halbiert. Das Interessante daran ist, dass eben die Werte von links und rechts immer wieder neu bestimmt werden und darüber schaffe ich es, immer nur in dem halbierten Bereich des vorherigen Schrittes zu suchen. Der Algorithmus ist zu Ende, wenn das Element gefunden wurde, oder wenn zum Schluss nur noch ein Element übrig ist. Entweder ist dieses letzte Element das gesuchte, oder das gesuchte Element kommt gar nicht vor. Ich wende hier diesen Algorithmus auf ein sortiertes Array an, ich suche nach der Zahl 42, die kommt vor, wie Sie sehen, und wir sollten die Suche einmal ausführen, aber hier macht es sehr viel Sinn, im Debug-Modus zu arbeiten. Ich gehe also auf "Menüleiste Run Debug", wechsele in die Debug-Perspektive und wir schauen uns an, welche Elemente, welche Variablen interessant sind: Natürlich das zu suchende Element, der Wert von links und rechts ergibt sich aus der Größe des Ursprungs-Arrays, das besteht aus 24 Elementen. Ich schaue, ob das Element in der Mitte, das ist der Wert 11, also das Element an der zwölften Position, gleich dem gesuchten Element ist. Das ist nicht so. Jetzt schaue ich: Ist dieses Element an der zwölften Position größer als das gesuchte Element? Das ist nicht so - oder eben kleiner und beachten Sie, wie sich jetzt die Mitte verändert. Ich bestimme nun den mittleren Wert des verbleibenden Arrays, das ist das Array auf der rechten Seite von meinem Original-Array. Und gehe diesen Schritt wieder durch. Sie sehen: Der Wert von Mitte wird wieder größer, also suche ich wieder auf der rechten Seite. Jetzt suche ich auf der linken Seite von meiner neuen Mitte und sobald das Element gefunden wurde, wird die Position zurückgeliefert und das hier ist der Index des gesuchten Elements. Sie haben also in diesem Video Such-Algorithmen im Allgemeinen und die binäre Suche und die lineare Suche im Speziellen kennengelernt.

Mathematik-Grundbegriffe für Programmierer

Lernen Sie die Themenbereiche und Verfahren aus der Mathematik kennen, die bei der täglichen Programmierarbeit zum Einsatz kommen.

2 Std. 54 min (40 Videos)
Derzeit sind keine Feedbacks vorhanden...
Exklusiv für Abo-Kunden
Erscheinungsdatum:03.10.2016
Aktualisiert am:19.12.2016

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!