Informatik Algorithmen – Binärsuche und Suchstrategien
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was ist die Zeitkomplexität der Binärsuche? · Welche Vorbedingung muss für Binärsuche…
Karten
15 KartenWas ist die Zeitkomplexität der Binärsuche?
Rückseite
Die Binärsuche hat eine Zeitkomplexität von O(log n), da der Suchraum bei jedem Schritt halbiert wird.
Welche Vorbedingung muss für Binärsuche erfüllt sein?
Rückseite
Das Array muss sortiert vorliegen – aufsteigend oder absteigend –, andernfalls liefert der Algorithmus falsche Ergebnisse.
Wie berechnet man den Mittelindex bei Binärsuche korrekt?
Rückseite
mid = low + (high - low) / 2 verhindert Integer-Überlauf bei großen Arrays im Gegensatz zu (low + high) / 2.
Was ist der Unterschied zwischen iterativer und rekursiver Binärsuche?
Rückseite
Beide haben O(log n) Zeitkomplexität, aber die iterative Variante nutzt O(1) Speicher, die rekursive O(log n) Stack-Speicher.
Wann ist lineare Suche der Binärsuche vorzuziehen?
Rückseite
Bei unsortierten Daten, sehr kleinen Arrays (n < 50) oder wenn nur ein einmaliger Zugriff nötig ist – Sortieraufwand lohnt sich sonst nicht.
Was bedeutet der Begriff Suchraum bei der Binärsuche?
Rückseite
Der Suchraum ist der Indexbereich [low, high], in dem das gesuchte Element noch liegen kann – er halbiert sich pro Iteration.
Wie verhält sich Binärsuche bei doppelten Elementen im Array?
Rückseite
Standard-Binärsuche findet beliebig eines der doppelten Elemente; für erstes/letztes Vorkommen braucht man modifizierte Varianten (Lower/Upper Bound).
Was ist der Invariant der Binärsuche?
Rückseite
Das gesuchte Element befindet sich – falls vorhanden – immer im aktuellen Intervall [low, high]; außerhalb wurde es ausgeschlossen.
Warum beendet sich Binärsuche bei low > high ohne Treffer?
Rückseite
Dann ist der Suchraum leer – low hat high überholt –, was beweist, dass das Element nicht im Array enthalten ist.
Wie unterscheidet sich Ternäre Suche von Binärsuche?
Rückseite
Ternäre Suche teilt den Suchraum in drei Teile, hat aber mehr Vergleiche pro Schritt und bringt keine asymptotische Verbesserung gegenüber Binärsuche.
Was ist Interpolationssuche und wann lohnt sie sich?
Rückseite
Interpolationssuche schätzt die Position über Wertverteilung, erreicht O(log log n) bei gleichverteilter Daten, degeneriert aber bei Clustern zu O(n).
Welchen Fehler macht man bei mid = (low + high) / 2 in C/Java?
Rückseite
Bei großen Indizes kann low + high den Integer-Überlauf verursachen und mid negativ werden – mid = low + (high - low) / 2 ist sicher.
Wie sucht man das erste Vorkommen eines Wertes per Binärsuche?
Rückseite
Bei Treffer high = mid - 1 weitersuchen und Ergebnis speichern – am Ende liegt der Index des ersten Vorkommens vor.
Was ist Exponentielle Suche und wie nutzt sie Binärsuche?
Rückseite
Exponentielle Suche verdoppelt den Index bis zum Überlauf, führt dann Binärsuche im letzten Intervall durch – ideal für unbeschränkte Arrays.
Warum ist Binärsuche auf verketteten Listen ineffizient?
Rückseite
Zufälliger Zugriff auf mid ist O(n), da man von Head traversieren muss – Gesamtlaufzeit wird O(n log n) statt O(log n).