Durchsuchen von Array-Listen

In diesem Beitrag beschäftigen wir uns mit dem Durchsuchen von Array-Listen. Dabei werden wir auf die zwei wesentlichen Suchverfahren eingehen. 

Lineare 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)

Binäre 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)

Beispiel:
Geuscht 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. 

Zusammenfassung
Durchsuchen von Array-Listen
Artikeltitel
Durchsuchen von Array-Listen
Beschreibung
In diesem Beitrag beschäftigen wir uns mit dem Durchsuchen von Array-Listen. Dabei werden wir auf die zwei wesentlichen Suchverfahren eingehen. 
Autor

Kommentare

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

E-Mail-Benachrichtigung bei weiteren Kommentaren.
Auch möglich: Abo ohne Kommentar.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden .

Pin It on Pinterest

Durch die weitere Nutzung der Seite stimmst du der Verwendung von Cookies zu. Weitere Informationen

Die Cookie-Einstellungen auf dieser Website sind auf "Cookies zulassen" eingestellt, um das beste Surferlebnis zu ermöglichen. Wenn du diese Website ohne Änderung der Cookie-Einstellungen verwendest oder auf "Akzeptieren" klickst, erklärst du sich damit einverstanden.

Schließen