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 -11function binarySearch(arr, target) { // Der Suchbereich ist anfangs das ganze Array: Indizes 0 bis length - 12 let left = 0;3 let right = arr.length - 1;4 // Wiederholt, solange der Bereich mindestens ein Element enthält5 while (left <= right) { // Index des mittleren Elements, abgerundet6 const mid = Math.floor((left + right) / 2);7 // Das mittlere Element ist target: Gibt seinen Index zurück8 if (arr[mid] === target) return mid; // Die Mitte ist zu klein, target kann also nur in der rechten Hälfte liegen9 if (arr[mid] < target) left = mid + 1; // Die Mitte ist zu groß, daher geht die Suche in der linken Hälfte weiter10 else right = mid - 1;11 }12 // Der Bereich ist leer: target ist nicht im Array13 return -1;14}15 // Binäre Suche funktioniert nur auf einem sortierten Array wie diesem16const sorted = [1, 3, 5, 7, 9, 11, 13, 15];// 7 wird gleich in der ersten Mitte (Index 3) gefunden, daher wird 3 ausgegeben17console.log(binarySearch(sorted, 7));// 8 ist nicht im Array, daher wird -1 ausgegeben18console.log(binarySearch(sorted, 8));// 1 ist das erste Element, daher wird 0 ausgegeben19console.log(binarySearch(sorted, 1));Ausgabe
3 -1 0
Ü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