Implementierung der binären Suche in JavaScript

Level 5421 Tastenanschläge

binarySearch sucht einen Wert in einem sortierten Array, indem es das mittlere Element prüft und den Bereich bei jedem Schritt halbiert. Es gibt 3 für 7, -1 für 8 (nicht vorhanden) und 0 für 1 aus.

JavaScript-Code

// Gibt den Index von target im sortierten Array arr zurück, sonst -1
1function binarySearch(arr, target) {
// Der Suchbereich ist anfangs das ganze Array: Indizes 0 bis length - 1
2 let left = 0;
3 let right = arr.length - 1;
4
// Wiederholt, solange der Bereich mindestens ein Element enthält
5 while (left <= right) {
// Index des mittleren Elements, abgerundet
6 const mid = Math.floor((left + right) / 2);
7
// Das mittlere Element ist target: Gibt seinen Index zurück
8 if (arr[mid] === target) return mid;
// Die Mitte ist zu klein, target kann also nur in der rechten Hälfte liegen
9 if (arr[mid] < target) left = mid + 1;
// Die Mitte ist zu groß, daher geht die Suche in der linken Hälfte weiter
10 else right = mid - 1;
11 }
12
// Der Bereich ist leer: target ist nicht im Array
13 return -1;
14}
15
// Binäre Suche funktioniert nur auf einem sortierten Array wie diesem
16const sorted = [1, 3, 5, 7, 9, 11, 13, 15];
// 7 wird gleich in der ersten Mitte (Index 3) gefunden, daher wird 3 ausgegeben
17console.log(binarySearch(sorted, 7));
// 8 ist nicht im Array, daher wird -1 ausgegeben
18console.log(binarySearch(sorted, 8));
// 1 ist das erste Element, daher wird 0 ausgegeben
19console.log(binarySearch(sorted, 1));

Ausgabe

3
-1
0
Diesen Code tippen üben

Übe, diesen Code zu tippen. Ergebnisse werden nicht in der Rangliste gespeichert.

Symbole in diesem Code

Die Symbole, die du in diesem JavaScript-Code tippst, und wie oft sie vorkommen.

  • (× 12
  • )× 12
  • ,× 11
  • ;× 11
  • =× 10
  • .× 5
  • -× 3
  • [× 3
  • ]× 3
  • {× 2

Weitere JavaScript-Beispiele auf Level 5

← JavaScript-Tippübungen