Suchalgorithmen Flashcards
Arten von Suchalgorithmen
Sequentielle Suche, Binäre Suche
Voraussetzungen für Sequentielle Suche
keine
Ablauf einer Sequentieller Suche
Vergleich von Suchschlüssel und Feldwert bei Index i
Inputparameter einer sequentiellen Suche
Feld und Suchschlüssel
Rückgabewert einer erfolgreichen Sequentiellen Suche
Index des ersten Feldwertes, der dem Suchschlüssel entspricht (nicht der Wert selbst)
Rückgabewert einer nicht erfolgreichen Sequentiellen Suche
-1 bzw. NO_KEY
Laufzeit Sequentielle Suche: im Bestfall
1
Laufzeit Sequentielle Suche: im Worst Case
n (Länge des Feldes)
Laufzeit Sequentielle Suche: im Durchschnitt (erfolgreiche Suche)
(n+1)/2 (Hälfte der um eins erhöhten Feldlänge)
Laufzeit Sequentielle Suche: im Durchschnitt (nicht erfolgreiche Suche)
n (in jedem Fall wird das gesamte Feld geprüft)
Voraussetzung Binäre Suche
sortiertes Feld (je nach Code auf- oder absteigend )
Inputparameter Binäre Suche
Feld, Suchschlüssel
Ablauf Binäre Suche
- Abgrenzung des Feldes
- Kontrolle des mittleren Feldelements
- neues Feld abgrenzen (entweder linkes oder rechtes Teilfeld)
- Schritte 1 bis 3 wiederholen
Abbruchbedingung Sequentiell Suche
Wert gefunden oder letztes Feldelement erreicht
Abbruchbedingung Binäre Suche
Wert gefunden oder Untergrenze ist größer als die Obergrenze
Welcher Index wird bei der Binären Suche untersucht, wenn das Feld keine genaue Mitte hat und warum?
immer den kleineren der “beiden Mitten” (weil der int-Wert der Mitte Nachkommazahlen fallen lässt)
Rückgabewert einer erfolgreichen Binären Suche
Index des ersten Feldwertes, der dem Suchschlüssel entspricht (nicht der Wert selbst)
Rückgabewert einer nicht erfolgreichen Binären Suche
-1 bzw. NO_KEY
Laufzeit Binäre Suche: im Bestfall
1
Laufzeit Binäre Suche: im Worst Case
log2(n)
Laufzeit Binäre Suche: im Durchschnitt (erfolgreiche Suche)
log2(n)
Laufzeit Binäre Suche: im Durchschnitt (nicht erfolgreiche Suche)
log2(n)
