Home > Informatik > Stufe Q1

12 Suchverfahren

Überblick - Lineare Suche - Binäre Suche - Binäre Suchbäume - Index- u. Interpolationssuche

Suchalgorithmen sind aus dem Alltag nicht heraus zudenken. Ständig wird irgendetwas gesucht, beispielsweise Internetadressen, Personen, Telefonnummern, Zeitungsartikel und so weiter. Suchen ist eine der häufigsten Aufgaben, die Computer durchführen[2].

Nach [1] unterscheidet man beim Suchen folgende Situationen:

  1. Die zu durchsuchenden Daten sind völlig unsortiert
  2. Die zu durchsuchenden Daten sind linear auf- oder absteigend sortiert
  3. Die zu durchsuchenden Daten sind such-freundlich sortiert

Wenn die zu durchsuchenden Daten gar nicht sortiert sind, kann man nur eine lineare oder sequentielle Suche anwenden. Das heißt, man beginnt stur beim ersten Element und arbeitet sich von vorne nach hinten durch, bis man entweder die Daten gefunden hat oder ohne Erfolg am Ende der Daten angekommen ist. "Lineare Suche" oder "sequentielle Suche" nennt man dieses Verfahren.

Sind die zu durchsuchenden Daten linear sortiert, kann man eine Reihe von mehr oder weniger intelligenten Suchverfahren anwenden, welche die Suche erheblich verkürzen. Wenn Sie Ihre Bücher beispielsweise nach Autoren sortiert haben, dann werden Sie bei der Suche nach "Helmich" sicherlich nicht ganz vorne bei "A" anfangen oder ganz hinten bei "Z". Hier wäre die "binäre Suche" als gutes Suchverfahren zu nennen.

Am besten ist es, wenn die Daten bereits such-freundlich sortiert sind, zum Beispiel in einem binären Suchbaum. Dann sind Sie mit sehr wenigen Suchschritten entweder bei den gesuchten Daten oder haben festgestellt, dass die Daten nicht vorhanden sind. Suchbäume werden allerdings erst ganz am Ende der Stufe Q1 behandelt, darum verschieben wir dieses Thema auf später.

In unserem Informatik-Kurs werden wir die drei grundlegende Suchverfahren besprechen, nämlich die lineare Suche, die binäre Suche und die Suche in einem binären Suchbaum. Am Ende beschäftigen wir uns noch kurz mit der Indexsuche und der Interpolationssuche, zwei besonders effektiven Suchverfahren.

Themen

Quellen:

  1. Hattenhauer: Informatik für Schule und Ausbildung, München 2010.
  2. Fischbeck, Boockmeyer, Neubert: Fit fürs Studium Informatik, Bonn 2017.
  3. Herold, Lurz, Wohlrag, Hopf: Grundlagen der Informatik, Hallbergmoos 2017.
  4. Balzert, Lehrbuch Grundlagen der Informatik, Heidelberg 1999.