3.3.1.1 Sequentielles Suchen

In einer Liste von Elemente kann es erforderlich sein, ein Element zu suchen.

Das Ergebnis der Suche kann sein:

  • True – das gesuchte Element ist in der Liste enthalten
  • False – das gesuchte Element ist nicht in der Liste enthalten

Unwichtig ist beim Suchen, wie oft das gesuchte Element in der Liste enthalten ist.

  • Es ist eine vollkommen andere Frage, wie oft das Element in der Liste zu finden ist.
Icon Beschreibung
Exkurs »Listen«

Variablen können Werte des Datentyps »list« zugewiesen werden. Die Werte werden Listen genannt.

In Python ist eine Liste eine Folge von Elementen eines Datentyps oder unterschiedlicher Datentypen.

Die Folge der Elemente der Liste wird in eckigen Klammen [ ] gesetzt:

  • [12, 8, -120, 34, -2, 0, 98, -235, -4, 54]
  • [-12, 1e2, -1.5E-3, 0, 4.5, 72]
  • ["rot", "grün", "blau"]
  • [-34, "Python", [1, 2, 3], 1e-2]

Auf die Element einer Liste wird über deren Index in der Liste zugegriffen:

  • liste = [12, 8, -120, 34, -2, 0, 98, -235, -4, 54]
    liste[0] ist 12, liste[1] ist 8, liste[2] ist -120, …, liste[9] ist 54
  • Wichtig ist, dass die Indizierung der Listenelemente stets mit der Nummer 0 beginnt.
    Beispielsweise heißt das, die Liste [3, 8, 0, 9, 56] hat 5 Elemente mit den Nummern 0 bis 4.

Eine besondere Liste ist die leere Liste [].

Sequentielles Suchen heißt, dass solange in der Liste gesucht wird bis das Element:

  • gefunden wird und daraufhin sofort die Suche beendet wird, auch wenn das gesuchte Element eventuell mehrfach in der Liste enthalten ist
  • nicht gefunden wird und somit die Suche beendet ist

In der Abbildung 1 ist ein Algorithmus des sequentellen Suchens dargestellt.

Bild 53
Abbildung 1: Algorithmus des sequentiellen Suchens

Das Kernstück des Algorithmus ist die while-Schleife.

  • Die in der Abbildung 2 dargestellte while-Schleife wird im Allgemeinen verwendet, wenn die Anzahl der Wiederholungen (Schleifendurchläufe) von vornherein nicht bekannt ist.
    • Bild 50
    Abbildung 2: Die while-Schleife
  • Die while-Schleife ist deshalb für das sequentielle Suchen geeignet, weil das Suchen sofort beendet wird, sobald das gesuchte Element erstmalig in der Liste gefunden wurde.
  • Nur in dem Fall, dass das gesuchte Element an der letzten Stelle in der Liste steht oder nicht in der Liste enthalten ist, muss die gesamte Liste durchlaufen werden.
Übung

Aufgabe A25

Durchlaufe Schritt für Schritt den Algorithmus auf der Suche nach:

  • 12
  • -235
  • 17

Programm »seqsuche.py«

Der Callback-Funktion »suchen« liegt der in der Abbildung 1 dargestellte Algorithmus zugrunde.

Quelltext der Callback-Funktion »suchen« 
liste=[12, 8, -120, 34, -2, 0, 98, -235, -4, 54]

# Callback-Funktion
def suchen():
    global liste
    try:
        gesucht=int(entry.get())
        gefunden=False
        i=0
        while i< len(liste) and not gefunden:
            if gesucht==liste[i]:
                gefunden=True
            else:
                i=i+1
        if gefunden==True:
            label2.config(text=f"{gesucht} gefunden.")
        else:
            label2.config(text=f"{gesucht} nicht gefunden.")        
    except ValueError:
        label2.config(text = "Falsche Eingabe!")
    entry.delete(0, tk.END)
Erklärungen zum Quelltext
1. Zeile Der Variable »liste « wird als Wert die Liste »[12, 8, -120, 34, -2, 0, 98, -235, -4, 54] « zugewiesen.
  • Sie ist eine sogenannte globale Variable, weil sie sich außerhalb der Callback-Funktion befindet.
4. bis 21. Zeile Die Callback-Funktion »suchen« wird deklariert.
5. Zeile Die globale Variable »liste« wird in die Callbeck-Funktion eingebunden.
6. bis 21. Zeile Die »,try« und »except« Ausnahmebehandlung der Eingaben erfolgt.
7. Zeile Der Variable »gesucht« wird die eingegebene Ganzzahl zugewiesen.
8. Zeile Der Variable »gefunden« wird wird der Wahrheitswert »False« zugewiesen.
9. Zeile Der sogenannten Laufvariable »i« wird die »0« zugewiesen.

Die Variable heißt deshalb Laufvariable, weil sie bevorzugt in der for-Schleife und while-Schleife zum Zählen verwendet wird.

10. bis 14. Zeile Die while-Schleife wird deshalb verwendet, weil die Anzahl der Schleifendurchläufe von Anfang an nicht bekannt ist.
  • Die Funktion »len(liste)« ermittelt die Anzahl der Elemente der Liste.
  • Hat die Variable »gefunden« den Wert »False«, dann ist »not gefunden« »True«.
14. Zeile Die Wertzuweisung »i=i+1« ist das Inkrement der Variable »i«.
  • Das heißt, der Wert der Variable »i« wird um 1 erhöht.
  • Gleichbedeutend mit »i=i+1« ist »i+=1«.
Icon Beschreibung
Exkurs »Wahrheitswerte«

Variablen können Werte des Datentyps »bool« zugewiesen werden (beispielsweise gewonnen = True).

Die beiden einzigen Werte »True« (wahr) und »False« (falsch) des Datentyps werden Wahrheitswerte genannt.

Logische Operatoren Vergleichsoperatoren
True and True ergibt True
True and False ergibt False
False and True ergibt False
False and False ergibt True 		Gleichheit: »==«
2 == 2 ist True
2 == 3 ist False
3 == 2 ist False
True or True ergibt True
True or False ergibt True
False or True ergibt True
False or False ergibt False 		Ungleichheit: !=
2 != 2 ist False
2 != 3 ist True
3 != 2 ist True
not True ergibt False
not False ergibt True
 Kleiner als: <
2 < 2 ist False
2 < 3 ist True
3 < 2 ist False
Kleiner gleich: <=
2 <= 2 ist True
2 <= 3 ist True
3 <= 2 ist False
Größer als: >
2 > 2 ist False
2 > 3 ist False
3 > 2 ist True
Größer gleich: >=
2 >= 2 ist True
2 >= 3 ist False
3 >= 2 ist True
Übung

Aufgabe A26

Implentiere ein Prgramm »seqsuche.py« am Computer.

Das Programm soll aus zwei Teilen bestehen:

  • der grafischen Benutzeroberfläche – dem Hauptfenster
Bild 54 Bild 55
Abbildung 3: Eine mögliche grafische Benutzeroberfläche
  • der Callback-Funktion »suchen«

Führe das Programm u. a. mit folgenden Eingaben aus und teste, ob es fehlerfrei läuft und den gestellten Anforderungen entspricht:

  • 12
  • -235
  • 17