Binary Search

Q: Wie hoch ist die Zeitkomplexität der binären Suche?

O(log n) . Jeder Vergleich halbiert den Bereich, in dem sich das Ziel noch befinden kann, sodass nach k Schritten höchstens n / 2^k Kandidaten übrig bleiben. Eine Liste mit 10^4 Elementen benötigt höchstens 14 Vergleiche, eine Liste mit 10^9 Elementen höchstens 30. Die iterative Version benötigt O(1) zusätzlichen Speicherplatz.

Q: Warum benötigt die binäre Suche ein sortiertes Array?

Der Schritt, bei dem die Hälfte der Liste verworfen wird, beruht auf der Reihenfolge. Wenn nums[mid] < target gilt, garantiert die Sortierung, dass auch jedes Element links von mid kleiner als target ist, sodass keines davon übereinstimmen kann. Bei einer unsortierten Liste sagt dieser Vergleich nichts über die anderen Elemente aus, und du musst sie alle überprüfen.

Q: Soll die binäre Suche iterativ oder rekursiv sein?

Beide sind korrekt und laufen in O(log n) -Zeit. Die rekursive Version ruft sich für eine Hälfte selbst auf und benötigt O(log n) Stack-Speicher; die iterative Version verschiebt lo und hi in einer Schleife und benötigt O(1) . Interviewer erwarten üblicherweise die Schleife, und sie vermeidet jedes Rekursionslimit.

Q: Wie vermeidest du einen Überlauf bei der Berechnung des mittleren Index?

Schreibe mid = lo + (hi - lo) / 2 statt (lo + hi) / 2 . Beide ergeben denselben Index, aber bei der zweiten Form werden zuerst zwei Indizes addiert, und bei einer 32-Bit-Ganzzahl läuft diese Summe über, sobald die Indizes etwa 1.07 × 10^9 überschreiten. Python und Ruby haben Ganzzahlen mit unbegrenzter Genauigkeit, daher ist dort die Kurzform sicher.

LeichtBinäre Suche

+10

Du erhältst eine Liste von Ganzzahlen nums, die aufsteigend sortiert ist und keine wiederholten Werte enthält, sowie eine Ganzzahl target. Gib den Index von target in nums zurück, beginnend bei 0, oder -1, wenn der Wert nicht in der Liste enthalten ist. Strebe eine Laufzeit von O(log n) an. Das bedeutet, dass du dir nicht jedes Element ansehen kannst.

Funktion

search(nums: integer-array, target: integer) → integer

numsinteger-array: die sortierte Liste unterschiedlicher Ganzzahlen
targetinteger: der zu suchende Wert
Gibt zurückinteger: der Index von target in nums oder -1, falls target nicht vorhanden ist

Einschränkungen

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums ist streng aufsteigend sortiert, daher kommt jeder Wert genau einmal vor.

Beispiele

Eingabe: nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
Ausgabe: 4
Erklärung: nums[4] ist 9. Die Suche betrachtet zuerst den Index 3 (Wert 4, zu klein), dann den Index 5 (Wert 15, zu groß) und schließlich den Index 4, wo sie 9 findet.

Eingabe: nums = [1, 3, 5, 8, 13, 21]target = 10
Ausgabe: -1
Erklärung: 10 läge zwischen 8 und 13, und keines von beiden ist 10, also ist es nicht in der Liste. Der Suchbereich verkleinert sich, bis lo hi überschreitet, und die Funktion gibt -1 zurück.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Wenn nums wiederholte Werte enthalten könnte, wie würdest du den ersten Index von target zurückgeben und dabei weiterhin in O(log n) bleiben?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Wenn du die Elemente einzeln durchgehst, findest du target, ignorierst aber die eine Tatsache, die das Problem interessant macht: Die Liste ist sortiert. Ein einziger Vergleich mit dem mittleren Element verrät dir, welche Hälfte noch target enthalten kann. So kannst du bei jedem Schritt die Hälfte der Kandidaten ausschließen. Für eine Liste mit 10^4 Elementen sind dann höchstens 14 Vergleiche nötig statt 10000.

Von links nach rechts scannen

Idee

Überprüfe jeden Index der Reihe nach und gib den ersten zurück, dessen Wert gleich target ist. Wenn die Schleife ohne Treffer endet, ist target nicht in der Liste, also gib -1 zurück. Jedes Element wird einmal verglichen, wodurch die Antwort für jede Liste korrekt ist, unabhängig davon, ob sie sortiert ist oder nicht.

Diese Allgemeingültigkeit ist das Problem. Eine Liste mit 10^4 Elementen erfordert bis zu 10000 Vergleiche, und der Aufwand wächst proportional zu n. Bei der Suche wird nicht berücksichtigt, dass nums sortiert ist, daher wird die von der Aufgabe geforderte Schranke O(log n) verfehlt. Du könntest abbrechen, sobald ein Wert größer als target ist, aber im schlimmsten Fall musst du trotzdem die gesamte Liste durchgehen.

Algorithmus

Vergleiche für jeden Index i von 0 bis n-1 nums[i] mit target.
Wenn sie gleich sind, gib i zurück.
Gib nach der Schleife -1 zurück.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Binäre Suche mit zwei Indizes

Idee

Behalte zwei Indizes, lo und hi, mit einer Zusicherung: Wenn target in der Liste vorkommt, liegt sein Index zwischen lo und hi, einschließlich. Zu Beginn umfasst dieser Bereich die gesamte Liste, von 0 bis n-1. Betrachte den mittleren Index mid. Wenn nums[mid] gleich target ist, bist du fertig. Ist der Wert kleiner, dann ist aufgrund der Sortierung der Liste auch jedes Element bis einschließlich mid kleiner; setze also lo auf mid + 1. Ist der Wert größer, setze hi auf mid - 1. Nach beiden Änderungen gilt die Zusicherung weiterhin.

Gehe das erste Beispiel durch: [-7, -2, 0, 4, 9, 15, 23] mit target = 9. Der Bereich von 0 bis 6 hat den Mittelpunkt 3 mit dem Wert 4, der zu klein ist; der Bereich wird also zu 4 bis 6. Der Mittelpunkt ist 5 und enthält den Wert 15, der zu groß ist; der Bereich wird also zu 4 bis 4. An Index 4 steht 9: Gib 4 zurück.

Wenn target fehlt, wird der Bereich immer kleiner, bis lo über hi hinausgeht. Der Bereich ist dann leer, die Zusicherung besagt, dass target nirgendwo vorkommt, und du gibst -1 zurück. Jeder Schritt halbiert den Bereich, daher läuft die Schleife höchstens etwa log2(n) + 1 Mal: 14 Schritte bei 10^4 Elementen. Zwei Indizes sind alles, was du an zusätzlichem Speicher benötigst.

Algorithmus

Setze lo = 0 und hi = n-1.
Berechne, solange lo ≤ hi gilt, mid = lo + (hi - lo) / 2.
Gib mid zurück, wenn nums[mid] gleich target ist.
Wenn nums[mid] < target gilt, setze lo = mid + 1; andernfalls setze hi = mid - 1.
Wenn die Schleife endet, gib -1 zurück.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1  # nums[mid] and everything left of it is too small
        else:
            hi = mid - 1  # nums[mid] and everything right of it is too big
    return -1

Stolperfallen und Grenzfälle

Die binäre Suche ist kurz, und fast jeder Fehler ist ein Off-by-one-Fehler an den Grenzen des Suchbereichs.

Die Schleife mit lo < hi ausführen, während hi beim letzten Index startet. Die Schleife endet, obwohl noch ein Kandidat ungeprüft ist, sodass nums = [5] mit target = 5 -1 zurückgibt. Bei einem inklusiven Bereich die Schleife mit lo ≤ hi ausführen.
Bei einem inklusiven Bereich zu lo = mid oder hi = mid wechseln. Wenn lo und hi benachbart sind, ist mid gleich lo, und der Bereich wird nie kleiner: eine Endlosschleife. Du hast nums[mid] bereits geprüft, also gehe mit mid + 1 oder mid - 1 darüber hinaus.
(lo + hi) / 2 mit einer Ganzzahl fester Breite berechnen. Die Summe läuft über, sobald die Indizes etwa 10^9 überschreiten. Die Grenzen hier liegen weit darunter, aber lo + (hi - lo) / 2 ist die sichere Gewohnheit.
lo zurückgeben, wenn target fehlt. Nach der Schleife ist lo die Einfügeposition, also ein gültiger Index und nicht -1.
Die Verschiebung in Lua und R vergessen. Ihre Listen beginnen bei 1, daher ist der zurückgegebene Index die Position minus 1.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität der binären Suche?

O(log n). Jeder Vergleich halbiert den Bereich, in dem sich das Ziel noch befinden kann, sodass nach k Schritten höchstens n / 2^k Kandidaten übrig bleiben. Eine Liste mit 10^4 Elementen benötigt höchstens 14 Vergleiche, eine Liste mit 10^9 Elementen höchstens 30. Die iterative Version benötigt O(1) zusätzlichen Speicherplatz.

Warum benötigt die binäre Suche ein sortiertes Array?

Der Schritt, bei dem die Hälfte der Liste verworfen wird, beruht auf der Reihenfolge. Wenn nums[mid] < target gilt, garantiert die Sortierung, dass auch jedes Element links von mid kleiner als target ist, sodass keines davon übereinstimmen kann. Bei einer unsortierten Liste sagt dieser Vergleich nichts über die anderen Elemente aus, und du musst sie alle überprüfen.

Soll die binäre Suche iterativ oder rekursiv sein?

Beide sind korrekt und laufen in O(log n)-Zeit. Die rekursive Version ruft sich für eine Hälfte selbst auf und benötigt O(log n) Stack-Speicher; die iterative Version verschiebt lo und hi in einer Schleife und benötigt O(1). Interviewer erwarten üblicherweise die Schleife, und sie vermeidet jedes Rekursionslimit.

Wie vermeidest du einen Überlauf bei der Berechnung des mittleren Index?

Schreibe mid = lo + (hi - lo) / 2 statt (lo + hi) / 2. Beide ergeben denselben Index, aber bei der zweiten Form werden zuerst zwei Indizes addiert, und bei einer 32-Bit-Ganzzahl läuft diese Summe über, sobald die Indizes etwa 1.07 × 10^9 überschreiten. Python und Ruby haben Ganzzahlen mit unbegrenzter Genauigkeit, daher ist dort die Kurzform sicher.

Python

def search(nums, target):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

nums = [-7, -2, 0, 4, 9, 15, 23]
target = 9

Erwartet