Implementierung der binären Suche in JavaScript

Sie durchsuchen ein sortiertes Array mit 100.000 Produktpreisen. Die in JavaScript integrierte Methode indexOf() prüft jedes Element von Anfang an — das sind potenziell 100.000 Vergleiche. Die binäre Suche schafft es in maximal 17. Dieser Unterschied zeigt, warum der JavaScript-Algorithmus für binäre Suche wichtig ist und warum es sich lohnt, ihn selbst zu schreiben — denn JavaScript bietet keine integrierte Methode für binäre Suche.

Dieser Artikel behandelt die Funktionsweise der binären Suche, wie man sowohl iterative als auch rekursive Versionen implementiert und wann man sie gegenüber der linearen Suche verwenden sollte.

Was ist binäre Suche und warum erfordert sie ein sortiertes Array?

Die binäre Suche ist ein Divide-and-Conquer-Algorithmus. Sie funktioniert, indem sie den Suchraum wiederholt halbiert, bis sie den Zielwert findet oder alle Möglichkeiten ausgeschöpft sind.

Der Haken dabei: Sie funktioniert nur bei sortierten Arrays. Der Algorithmus geht davon aus, dass sich das Ziel in der rechten Hälfte befinden muss, wenn es größer als das mittlere Element ist. Diese Annahme bricht bei unsortierten Daten vollständig zusammen — Sie würden falsche Ergebnisse ohne Fehlermeldung erhalten.

Die Schritte sind:

1. Finden Sie das mittlere Element des aktuellen Suchbereichs
2. Wenn es dem Ziel entspricht, geben Sie seinen Index zurück
3. Wenn das Ziel kleiner ist, durchsuchen Sie die linke Hälfte
4. Wenn das Ziel größer ist, durchsuchen Sie die rechte Hälfte
5. Wiederholen Sie den Vorgang, bis es gefunden wird oder der Suchbereich leer ist

Implementierung der binären Suche in JavaScript: Iterativer Ansatz

Die iterative Version verwendet eine while-Schleife und zwei Zeiger. Sie ist der bevorzugte Ansatz für die meisten Fälle — lesbar, effizient und verwendet O(1) Speicherplatz.

function binarySearch(arr, target) {
  let start = 0
  let end = arr.length - 1

  while (start <= end) {
    const mid = Math.floor((start + end) / 2)

    if (arr[mid] === target) {
      return mid // Return the index
    } else if (arr[mid] < target) {
      start = mid + 1 // Search right half
    } else {
      end = mid - 1 // Search left half
    }
  }

  return -1 // Target not found
}

const prices = [10, 25, 47, 89, 134, 200]
console.log(binarySearch(prices, 89))  // 3
console.log(binarySearch(prices, 50))  // -1

Beachten Sie, dass dies den Index des Ziels zurückgibt, nicht einen Boolean-Wert. Das ist in der Praxis fast immer nützlicher.

Rekursive binäre Suche in JavaScript

Die rekursive Version übergibt bei jedem Aufruf aktualisierte Grenzindizes. Sie ist elegant, verwendet aber O(log n) Stack-Speicher — einen Frame pro rekursivem Aufruf.

function binarySearchRecursive(arr, target, start = 0, end = arr.length - 1) {
  if (start > end) return -1

  const mid = Math.floor((start + end) / 2)

  if (arr[mid] === target) return mid

  return arr[mid] < target
    ? binarySearchRecursive(arr, target, mid + 1, end)
    : binarySearchRecursive(arr, target, start, mid - 1)
}

const scores = [3, 11, 22, 45, 67, 91]
console.log(binarySearchRecursive(scores, 22))  // 2
console.log(binarySearchRecursive(scores, 50))  // -1

Ein häufiger Fehler: Das Vergessen des return beim rekursiven Aufruf. Ohne dieses gibt die Funktion undefined zurück, selbst wenn das Element existiert.

Sortieren vor der Suche

Wenn Ihr Array noch nicht sortiert ist, müssen Sie es zuerst sortieren. JavaScripts Standard-Array.sort() sortiert lexikografisch, was numerische Vergleiche zunichte macht:

[10, 9, 100].sort()                   // [10, 100, 9] — falsch
[10, 9, 100].sort((a, b) => a - b)    // [9, 10, 100] — richtig

Verwenden Sie immer einen numerischen Komparator für Zahlen-Arrays, bevor Sie die binäre Suche ausführen.

Binäre Suche vs. lineare Suche: Wann welche verwenden?

Bei einem Array mit 10.000 Elementen benötigt die lineare Suche bis zu 10.000 Vergleiche. Die binäre Suche benötigt maximal 14. Wenn Sie einmal durch ein kleines, unsortiertes Array suchen, ist indexOf() in Ordnung. Wenn Sie wiederholt durch große sortierte Daten suchen, ist die binäre Suche das richtige Werkzeug.

Fazit

Die binäre Suche ist in JavaScript einfach zu implementieren, sobald Sie die Anforderung an sortierte Arrays verstanden haben. Verwenden Sie standardmäßig die iterative Version — sie ist übersichtlicher und vermeidet den Overhead des Call-Stacks. Verwenden Sie die rekursive Version, wenn die Struktur Ihres Codes davon profitiert, aber denken Sie daran, immer den rekursiven Aufruf mit return zurückzugeben. Und überprüfen Sie immer, ob Ihr Array mit einem geeigneten numerischen Komparator sortiert ist, bevor Sie suchen.

Häufig gestellte Fragen (FAQs)

Complete picture for complete understanding

Capture every clue your frontend is leaving so you can instantly get to the root cause of any issue with OpenReplay — the open-source session replay tool for developers. Self-host it in minutes, and have complete control over your customer data.

Check our GitHub repo and join the thousands of developers in our community.