Durchsuchen von Array-Listen – Lineare und Binäre Suche

Aktualisiert am:

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:

  1. das gesuchte Element wurde gefunden. 
  2. das gesuchte Element ist größer ⇒ wiederhole die Suche in der rechten Hälfte der Datenmenge.
  3. das gesuchte Element ist kleiner ⇒ wiederhole die Suche in der Linken Hälfte der Datenmenge.

Effizienzklasse: O(log n)

Durchsuchen von Array Listen - Die Binäre-Suche
Durchsuchen von Array Listen – Die Binäre-Suche

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

Schreibe einen Kommentar

Notify me of followup comments via e-mail. You can also subscribe without commenting.