Einleitung
In diesem Beitrag beschäftigen wir uns mit dem Durchsuchen von Array-Listen und gehen näher auf das lineare und binäre Suchverfahren ein.
Durchsuchen von Array-Listen mit der linearen Suche
Eine lineare Suche durchläuft alle Elemente der Reihe nach und prüft, ob das gegeben Suchkriterium für das aktuelle Element gilt. Üblicherweise wird am Ende der List – falls kein passendes Element gefunden wurde – „-1″ zurückgegeben. Dieses Suchverfahren eignet sich am besten für unsortierte Listen der für Listen, über die keine zusätzlichen Informationen existieren, wie ihre Elemente angeordnet bzw. sortiert sind.
Effizienzklasse: O(n)
Durchsuchen von Array-Listen mit der binären Suche
Eine effizientere Methode zum Suchen in Datenstrukturen, speziell in sortierten Array-Listen, ist die binäre Suche. Jedoch ist es notwendig, dass die Elemente der Liste in einer sortierten Reihenfolge vorliegen. Bei der binären Suche wird immer das mittlere Element der Datenmenge betrachtet., dabei gibt es grundsätzlich drei Möglichkeiten:
- das gesuchte Element wurde gefunden.
- das gesuchte Element ist größer ⇒ wiederhole die Suche in der rechten Hälfte der Datenmenge.
- das gesuchte Element ist kleiner ⇒ wiederhole die Suche in der Linken Hälfte der Datenmenge.
Effizienzklasse: O(log n)
Beispiel:
Gesucht ist das Element „7″ in einer Liste aus 9 Elementen. Um das gesuchte Element zu finden sind 3 Schritte notwendig. Zuerst betrachten wir das Element in der Mitte unserer Array-Liste. Die „10″ ist offensichtlich nicht unser gesuchtes Element, außerdem ist unser gesuchtes Element kleiner, weshalb wir die Suche in der linken Hälfte unsere Array-Liste wiederholen müssen. Im nächstes Schritt ist die „8″ das Element, welches wir als nächstes betrachten. Wieder ist es offensichtlich nicht unser gesuchtes Element und außerdem gilt „7<8″, weshalb wir die Suche erneut in der linken Hälfte durchführen müssen. Und nun finden wir unser gesuchtes Element, bis hier hin hat es lediglich drei Schritte gebraucht.
Jetzt denkt man sich: „Moment! Die lineare Suche hätte dieses Element bereits nach dem zweiten Schritt gefunden.” Das ist korrekt, jedoch handelt es sich hier um einen „best-case” der linearen Suche, im „worst-case” muss auch diese alle Elemente unsere Array-Liste durchsuchen. Die binäre Suche hingegen wird das zu suchende Element immer in „log n”-Schritten finden, wobei „n” die Anzahl der Elemente in der Array-Liste sind.
Weitere Beiträge aus dieser Serie
- Binäre Suchbäume in der Informatik einfach erklärt
- Durchsuchen von Array-Listen - Lineare und Binäre Suche
- Sequentielle Datentypen
- Algorithmische Techniken - Brute Force, Greedy, Teile und Herrsche, Dynamische Programmierung und Backtracking
- Lazy Evaluation und Streams
- Die Liste als abstrakter Datentyp
- Korrektheitsbeweise von Klassen und Schleifen
- Der Graph als abstrakter Datentyp
