Binäre Suche in JavaScript

Die binäre Suche ist ein Suchalgorithmus, der verwendet wird, um die Position eines bestimmten Elements in einer sortierten Liste zu finden. Es funktioniert durch wiederholtes Teilen der Liste in zwei Hälften, bis das gewünschte Element gefunden wird oder festgestellt wird, dass das Element nicht in der Liste vorhanden ist.

Wie funktioniert die binäre Suche?

Um zu verstehen, wie die binäre Suche funktioniert, betrachten wir ein Beispiel. Angenommen, wir haben eine sortierte Liste von ganzen Zahlen und möchten die Position der Zahl 37 finden. So würde der binäre Suchalgorithmus funktionieren:

1. Zuerst bestimmen wir das mittlere Element der Liste. Wenn das mittlere Element 37 ist, sind wir fertig und geben die Position des Elements zurück.
2. Wenn das mittlere Element nicht 37 ist, prüfen wir, ob es größer oder kleiner als 37 ist. Wenn es größer als 37 ist, wissen wir, dass das gewünschte Element in der linken Hälfte der Liste stehen muss. Wenn es weniger als 37 ist, wissen wir, dass das gewünschte Element in der rechten Hälfte der Liste stehen muss.
3. Wir wiederholen den Vorgang für die entsprechende Hälfte der Liste, bis das Element gefunden wird oder festgestellt wird, dass das Element nicht in der Liste vorhanden ist.

function binarySearch(arr, x) {
  let start = 0;
  let end = arr.length - 1;
  
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    
    if (arr[mid] === x) {
      return mid;
    }
    else if (arr[mid] < x) {
      start = mid + 1;
    }
    else {
      end = mid - 1;
    }
  }
  
  return -1;
}

let arr = [1, 3, 5, 7, 9, 11, 13];
let x = 5;

console.log(binarySearch(arr, x)); // Output: 2

Warum sollten wir die binäre Suche verwenden?

Warum sollten wir also die binäre Suche verwenden? Einer der Hauptvorteile der binären Suche ist ihre Zeitkomplexität. Im schlimmsten Fall beträgt die Zeitkomplexität der binären Suche O(log n), was bedeutet, dass sie für große Listen viel schneller ist als die lineare Suche (O(n)). Dies macht es zu einem effizienten Algorithmus zum Durchsuchen großer Datensätze.

Zusammenfassend lässt sich sagen, dass die binäre Suche ein nützlicher Algorithmus ist, um schnell die Position eines bestimmten Elements in einer sortierten Liste zu finden. Aufgrund seiner zeitlichen Komplexität eignet es sich zum Durchsuchen großer Datenmengen und ist relativ einfach in JavaScript zu implementieren.