ENDEAR
Kostenlos starten
Algorithmuspro

Binäre Suche

Finde einen Wert in einem sortierten Array, indem du den Suchbereich bei jedem Schritt halbierst.

Zeit
O(log n)
Speicher
O(1)

// Schritt für Schritt

Schritt 1 / 9
1function binarySearch(nums, target) {2  let lo = 0, hi = nums.length - 1;3  while (lo <= hi) {4    const mid = Math.floor((lo + hi) / 2);5    if (nums[mid] === target) return mid;6    if (nums[mid] < target) lo = mid + 1;7    else hi = mid - 1;8  }9  return -1;10}
target
= 7
  1. 1lo
  2. 3
  3. 5
  4. 7
  5. 9
  6. 11
  7. 13
  8. 15
  9. 17hi

Das Array ist sortiert. Durchsuche den ganzen Bereich: lo = 0, hi = 8.

// pro-lektion

Den ganzen Durchlauf freischalten

Diese Lektion ist Teil von Pro. Pro schaltet jeden Schritt jeder Lektion frei, dazu Muster-Übungen und Fortschrittsauswertungen.

Preise ansehen

So funktioniert es

Schau auf die Mitte des Bereichs. Ist sie das Ziel, bist du fertig. Ist sie zu klein, kann das Ziel nur in der rechten Hälfte liegen; ist sie zu groß, nur in der linken. Weil sich der Bereich jedes Mal halbiert, reichen etwa log₂ n Vergleiche, selbst bei Millionen von Einträgen.