Veröffentlicht · wird verbessert
Algorithm
Suchverfahren finden Werte oder Positionen in Daten: lineare Suche, binäre Suche, lower_bound und upper_bound, Binärsuche über die Antwort und Hash-Zugriffe.
Suchen bedeutet, in einer Datensammlung einen Wert zu finden oder die Position, an der eine Bedingung zum ersten Mal erfüllt ist. Die lineare Suche prüft die Elemente nacheinander und funktioniert mit beliebigen Daten. Die binäre Suche halbiert einen sortierten Bereich in jedem Schritt und braucht selbst bei einer Million Elementen nur etwa 20 Vergleiche. Für Abfragen auf exakt gleiche Schlüssel liefert eine Hashtabelle im Mittel konstante Zeit.
Suchen ist grundlegend, weil fast jedes Programm etwas nachschlägt: Datenbankindizes, Autovervollständigung, Loganalyse und Routingtabellen beruhen darauf. Die binäre Suche ist außerdem nicht auf Arrays beschränkt. Sobald eine Ja/Nein-Bedingung über einem Bereich nur einmal umschlägt, lässt sich die Antwort selbst binär suchen. So werden viele Optimierungsaufgaben aus Programmierinterviews zu kurzem, verlässlichem Code.
Am besten schreibt man zuerst eine lineare Suche und eine binäre Suche mit geschlossenem Intervall selbst und übt danach die Formen lower_bound und upper_bound mit halboffenem Intervall, bis die Randbehandlung sitzt. Verfolgen Sie kleine Arrays von Hand, prüfen Sie Ihren Code mit Zufallseingaben gegen das Python-Modul bisect und üben Sie anschließend Binärsuche über die Antwort und ternäre Suche an Optimierungsaufgaben.
Vergleicht die Elemente nacheinander in O(n) Zeit. Sie braucht keine Sortierung und ist bei kleinen Datenmengen oft die schnellste Wahl.
Halbiert einen sortierten Bereich in jedem Schritt und findet Werte in O(log n) Zeit. Iterativ umgesetzt braucht sie nur O(1) zusätzlichen Speicher.
Liefern die erste Position, deren Wert mindestens so groß bzw. echt größer als der gesuchte ist. Ihre Differenz zählt Duplikate; das Python-Modul bisect bietet beide an.
Die parametrische Suche macht aus der Frage nach dem kleinsten zulässigen Wert einen Ja/Nein-Test und durchsucht den Bereich möglicher Antworten binär.
lower_bound liefert den ersten Index, dessen Wert mindestens x ist, und arbeitet dabei mit dem halboffenen Bereich [lo, hi). Ist der mittlere Wert kleiner als x, wird die linke Hälfte verworfen, sonst die rechte. contains prüft mit diesem Index, ob der Wert vorkommt, und die letzte Zeile bestätigt, dass das Ergebnis mit bisect.bisect_left aus der Standardbibliothek übereinstimmt.
searching.py
from bisect import bisect_left
def lower_bound(a, x):
"""Return the first index i with a[i] >= x (len(a) if there is none)."""
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def contains(a, x):
i = lower_bound(a, x)
return i < len(a) and a[i] == x
if __name__ == "__main__":
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(lower_bound(data, 23), contains(data, 23)) # 5 True
print(lower_bound(data, 24), contains(data, 24)) # 6 False
print(lower_bound(data, 24) == bisect_left(data, 24)) # True
python searching.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Suchen.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Suchen aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.