Suchalgorithmen

Agenda

  • Intro
  • Lineare Suche
  • Binärsuche
  • Interpolationssuche
  • Two Chrystal Balls Problem

Intro

Was ist Suchen?

Auffinden eines bestimmten Elements innerhalb einer Datensammlung

Begriffe

  • Zielelement
  • Suchraum

Anwendungen von Suchalgorithmen

  • Suchmaschinen
  • Datenbanksysteme
  • E-Commerce
  • Musteranalyse

Lineare Suche

Funktionsweise

Die lineare Suche beginnt an einem Ende des Suchraumes und durchläuft jedes Element, bis das Zielelement gefunden wird.

Theoretisches Konzept

  • Jedes Element kann mit dem Suchkriterium übereinstimmen und wird überprüft.
  • Wenn das Zielelement gefunden wurde, wird der Index des Zielelements zurückgegeben.
  • Wenn das Zielelement nicht gefunden wurde, wird -1 zurückgegeben.

Demo - Linear Search

Performance

  • Zeitkomplexität: O(N)
  • Speicherkomplexität: O(1)

Zusammenfassung

  • Kann unabhänging von Sortierung benutzt werden
  • Kein weiterer Speicherbedarf
  • Geeignet für kleine Datenmengen

Binäre Suche

Funktionsweise

Die binäre Suche setzt einen sortierten Suchraum voraus, was die Suche erheblich vereinfacht.

Wird ein Element innerhalb des Suchraumes mit dem Zielelement verglichen, kann abgeleited werden, ob das Zielelement vor oder nach dem Element sein muss.

Theoretisches Konzept

  1. Mitte des aktuellen Suchraumes finden
  2. Wenn Element in der Mitte dem Suchkriterium entspricht → index zurückgeben.
  3. Wenn Element in der Mitte größer als Suchkriterium → in erster Hälfte weitersuchen
  4. Wenn Element in der Mitte kleiner als Suchkriterium → in zweiter Hälfte weitersuchen
  5. Wenn kein Element im Suchraum gefunden wurde → -1 zurückgeben

Begriffe - Binäre Suche

  • high = index oberes Ende des Suchraumes
  • low = index unteres Ende des Suchraumes
  • middle = index Mitte des Suchraumes
  • Beispiel

Demo - Binary Search

  • low/high/middle
  • gefunden/größer/kleiner
  • while bedingung/nicht gefunden

Interpolations Suche

Funktionsweise

Die Interpolationsuche setzt einen sortierten Suchraum voraus, was die Suche erheblich vereinfacht.

Handelt es sich um eine gleichverteilung der Daten, kann mit der linearen Interpolation der Suchraum besser eingeschränkt werden.

Theoretisches Konzept

  1. Bessere Mitte des Suchraumes finden (lineare interpolation)
  2. Rest wie Binäre Suche

Lineare Interpolation

Demo - Interpolationssuche

  • middle Index anpassen
  • while Bedingung anpassen

Vergleich Suchalgorithmen

Lineare Suche vs Binäre Suche

LinearBinaryInterpolation
Sortierung irrelevantSortierung notwendigSortierung notwendig
Zeit: O(N)Zeit: O(log N)Zeit: O(N)

abhängig von Anwendungsfall

Rest of the day

  • Problem und Datensatz
  • Search mit eigenem Problem (Optional)