Beherrschen der binären Suche in JavaScript und Java: Eine Schritt-für-Schritt-Anleitung

Die binäre Suche ist ein grundlegender Algorithmus, den jeder Entwickler verstehen sollte. Er bietet eine äußerst effiziente Möglichkeit, nach Elementen in einem sortierten Array zu suchen. Dieser Algorithmus basiert auf einem „Teile-und-herrsche“-Ansatz, der es ihm ermöglicht, den Suchraum mit jedem Schritt zu halbieren. In diesem Artikel untersuchen wir die binäre Suche in JavaScript und Java und behandeln iterative und rekursive Implementierungen.

Was ist binäre Suche?

Binäre Suche ist ein Algorithmus, der entwickelt wurde, um die Position eines Zielwerts innerhalb eines sortierten Arrays zu finden. Durch die Ausnutzung der Sortierung des Arrays schränkt die binäre Suche den Suchraum effizient ein und erreicht eine zeitliche Komplexität von O(log n). Dies ist viel schneller als eine lineare Suche in großen Datensätzen.

Hier ist eine allgemeine Übersicht:

1. Beginnen Sie mit zwei Zeigern, startIndex und endIndex, die den aktuellen Suchbereich darstellen.
2. Berechnen Sie den mittleren Index (midIndex) zwischen startIndex und endIndex.
3. Vergleichen Sie das mittlere Element mit dem Ziel:
   • Wenn es mit dem Ziel übereinstimmt, geben Sie den Index zurück.
   • Wenn das mittlere Element größer als das Ziel ist, muss sich das Ziel in der linken Hälfte befinden, also passen Sie endIndex an.
   • Wenn das mittlere Element kleiner als das Ziel ist, muss sich das Ziel in der rechten Hälfte befinden, also passen Sie startIndex an.
4. Wiederholen Sie den Vorgang, bis das Ziel gefunden ist oder startIndex endIndex überschreitet, was anzeigt, dass das Ziel nicht im Array ist.

Lassen Sie uns in die Codebeispiele eintauchen.

---

Iterative binäre Suche in JavaScript und Java

Für diejenigen unter Ihnen, die eine Schleife lieben.

JavaScript-Implementierung

In JavaScript verwendet der iterative Ansatz eine Schleife, um eine binäre Suche durchzuführen. So sieht es aus:

const binarySearch = (arr, target) => {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] === target) {
      return midIndex; // Target found
    } else if (arr[midIndex] < target) {
      startIndex = midIndex + 1; // Search in the right half
    } else {
      endIndex = midIndex - 1; // Search in the left half
    }
  }
  return -1; // Target not found
};

let nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Java-Implementierung

In Java ist die iterative Implementierung ziemlich ähnlich, mit Anpassungen für die Java-Syntax:

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;

            if (arr[midIndex] == target) {
                return midIndex; // Target found
            } else if (arr[midIndex] < target) {
                startIndex = midIndex + 1; // Search in the right half
            } else {
                endIndex = midIndex - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;

        int result = binarySearch(nums, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

Erläuterung

In beiden Implementierungen:

• Wir setzen startIndex und endIndex auf den Anfang bzw. das Ende des Arrays.
• Jede Iteration findet den mittleren Index, midIndex, und vergleicht arr[midIndex] mit dem Ziel.
  • Wenn arr[midIndex] gleich target ist, geben wir midIndex zurück.
  • Wenn arr[midIndex] kleiner als der Zielwert ist, verschieben wir startIndex auf midIndex 1 und schränken die Suche auf die rechte Hälfte ein.
  • Wenn arr[midIndex] größer als das Ziel ist, verschieben wir endIndex auf midIndex - 1 und schränken die Suche auf die linke Hälfte ein.
• Die Schleife wird beendet, wenn startIndex endIndex überschreitet, was bedeutet, dass sich das Ziel nicht im Array befindet.

---

Rekursive Binärsuche in JavaScript und Java

Für den rekursiven Ansatz definieren wir die Funktion so, dass sie sich selbst mit aktualisierten Indizes aufruft, bis das Ziel gefunden wird oder der Suchbereich leer ist.

Für diejenigen unter Ihnen, die eine Gründung lieben.

JavaScript-Implementierung

In JavaScript ist hier eine rekursive binäre Suchimplementierung:

const binarySearch = (arr, target) => {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] === target) {
      return midIndex; // Target found
    } else if (arr[midIndex] < target) {
      startIndex = midIndex + 1; // Search in the right half
    } else {
      endIndex = midIndex - 1; // Search in the left half
    }
  }
  return -1; // Target not found
};

let nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Java-Implementierung

In Java kann eine ähnliche rekursive binäre Suche wie folgt implementiert werden:

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;

            if (arr[midIndex] == target) {
                return midIndex; // Target found
            } else if (arr[midIndex] < target) {
                startIndex = midIndex + 1; // Search in the right half
            } else {
                endIndex = midIndex - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;

        int result = binarySearch(nums, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

So funktioniert die rekursive Version

Bei jedem rekursiven Aufruf:

• Der mittlere Index, midIndex, wird berechnet.
• Wenn arr[midIndex] mit dem Ziel übereinstimmt, wird der Index zurückgegeben.
• Wenn arr[midIndex] größer als das Ziel ist, wird die Suche in der linken Hälfte fortgesetzt (endIndex wird zu midIndex - 1).
• Wenn arr[midIndex] kleiner als das Ziel ist, wird die Suche in der rechten Hälfte fortgesetzt (startIndex wird zu midIndex 1).
• Der Basisfall if (startIndex > endIndex) stellt sicher, dass die Rekursion stoppt, wenn das Ziel nicht gefunden wird.

  ---

  Komplexitätsanalyse

  • Zeitkomplexität: Sowohl die iterative als auch die rekursive Version haben eine Zeitkomplexität von O(log n), da jeder Schritt den Suchraum halbiert.
  • Raumkomplexität: Der iterative Ansatz ist O(1) für Raum, während der rekursive Ansatz aufgrund des Aufrufstapels eine Raumkomplexität von O(log n) aufweist.

  Wann sollte die binäre Suche verwendet werden?

  Binäre Suche ist ideal, wenn:

  • Das Array ist sortiert: Die binäre Suche funktioniert nur bei sortierten Arrays.
  • Effizienz ist entscheidend: Seine O(log n)-Zeitkomplexität ist für große Datensätze äußerst effizient.

  Wenn das Array unsortiert ist, sollten Sie erwägen, es zuerst zu sortieren (mit O(n log n)-Kosten) oder eine lineare Suche zu verwenden, wenn der Datensatz klein ist.

  ---

  Abschluss

  Die binäre Suche ist ein vielseitiger und effizienter Algorithmus zum Auffinden von Elementen in sortierten Arrays. Unabhängig davon, ob Sie sich für den iterativen oder den rekursiven Ansatz entscheiden, ist das Verständnis der binären Suche für die Verbesserung der Leistung Ihrer Anwendungen hilfreich. Probieren Sie beide Implementierungen in JavaScript und Java aus, um ein Gefühl dafür zu bekommen, wie sie funktionieren, und finden Sie heraus, welche für Ihren spezifischen Anwendungsfall am besten geeignet ist.

  ---

  ? Referenz

  • Binäre Suche
  • Grookking-Algorithmen
  • Big-O-Notation

  ? Sprechen Sie mit mir

  • LinkedIn
  • Github
  • Portfolio

  Das obige ist der detaillierte Inhalt vonBeherrschen der binären Suche in JavaScript und Java: Eine Schritt-für-Schritt-Anleitung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!