3.3.3 Sortieren und Suchen

Binäres Suchen – zuerst sortieren und dann suchen

Das binäre Suchen benötigt als Voraussetzung:

  • die sortierte Liste, in der gesucht werden soll (je nach den Elementen in der Liste aufsteigend, absteigend, alphabetisch oder lexikographfisch)
  • die Liste wird wiederholt halbiert

In der Abbildung 1 ist der Algorithmus des binären Suchens dargestellt, wobei die Elemente (Ganzzahlen) in der Liste »liste2« aufsteigend sortiert sind.

Bild 65
Abbildung 1: Darstellung desn Algorithmus

In den Tabellen 1 und 2 ist Schritt für Schritt die Suche nach den Ganzzahlen -120 und 100 in der aufsteigend sortierten Liste [-235, -120, -4, -2, 0, 8, 12, 34, 54, 98] dokumentiert.

Bild 66
Tabelle 1: Gesucht wird -120 und gefunden
Bild 66
Tabelle 2: Gesucht wird 100 und nicht gefunden
Übung

Aufgabe A34

Durchlaufe Schritt für Schritt den in der Abbildung 1 dargestellten Algorithmus, um in der Liste [-235, -120, -4, -2, 0, 8, 12, 34, 54, 98] die folgenden Ganzzahlen zu suchen:

  • 0
  • 54
  • 100
  • -235
  • -300

Dokumentiere die Suche in Tabellen – so wie in den Tabellen 1 und 2.

Beantworte die Frage, weshalb die Elemente (Ganzzahlen) der Liste für das Suchen sortiert sein müssen.

Übung

Aufgabe 35

Implementiere ein Programm »binsuche.py« am Computer.

Das Programm soll aus vier Teilen bestehen:

  • der Callback-Funktion »eingeben«, um die Elemente (Ganzzahlen) der Liste »liste1« einzugeben
  • der Callback-Funktion »sortieren«, um die Liste »liste1« mit Hilfe der Methode
    »liste2=sorted(liste1)« in die sortierte Liste »liste2« zu überführen
  • der Callback-Funktion »suchen«, um in der sortierten Liste »liste2« nach einer Ganzahl »gesucht« zu suchen
  • der grafischen Benutzeroberfläche – dem Hauptfenster den darauf platzierten mit Widgets

Führe das Programm aus und teste, ob es fehlerfrei läuft und den gestellten Anforderungen entspricht.

  • Eingeben der Ganzzahlen 54, 0, 34, -120, 8, -235, 8, 98, -2, 12 als Elemente in die Liste »liste1«
  • Sortieren, indem die Liste »liste1« die sortierte Liste »liste2« überführt wird
  • Suchen, indem u. a. die folgenden Ganzzahl in der sortierten Liste »liste2« gesucht werden:
  • 0
  • 54
  • 100
  • -235
  • -300

In der Abbildung 2 ist eine mögliche grafische Benutzeroberfläche des Programms – das Hauptfenster mit den darauf platzierten Widgets – dargestellt.

Bild 68
Abbildung 2: Screenshot des Hauptfensters[1]
  1. [1] Das Hauptfenster kann selbstverständlich auch anders und farbenfroher gestaltet werden.