Effizientes Suchen: Binäre Suche & Mehr

Suchen ist das A und O der Algorithmen. Während die lineare Suche $O(n)$ benötigt, ermöglicht uns die Binäre Suche, Elemente in $O(\log n)$ zu finden, indem der Suchraum wiederholt halbiert wird.

1. Klassische Binäre Suche

Wird verwendet, um einen Wert in einem sortierten Array zu finden.

function binarySearch(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    // Vermeiden Sie (left + right) / 2, um Überlauf in einigen Sprachen zu verhindern
    const mid = Math.floor(left + (right - left) / 2);

    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

[!WARNING] Stack-Überlauf / Präzision: In JavaScript sind Zahlen 64-Bit-Floats, daher ist $2^{53}-1$ die Grenze für sichere Ganzzahlen. In Sprachen wie Java oder C++ kann (left + right) / 2 einen int überlaufen lassen. Die Verwendung von left + (right - left) / 2 ist eine universell bewährte Methode.

2. Suchen in einer sortierten 2D-Matrix

Diese Matrix hat zwei Eigenschaften:

1. Jede Zeile ist sortiert.
2. Das erste Element jeder Zeile ist größer als das letzte Element der vorherigen Zeile.

Das bedeutet, die gesamte Matrix verhält sich wie ein einziges sortiertes Array.

/**
 * Sucht effizient nach einem Wert in einer sortierten m x n Matrix.
 * Zeitkomplexität: O(log(m * n))
 */
function searchMatrix(matrix: number[][], target: number): boolean {
  if (!matrix.length || !matrix[0].length) return false;

  const rows = matrix.length;    // Anzahl der Zeilen (äußere Arrays)
  const cols = matrix[0].length; // Anzahl der Spalten (Größe der inneren Arrays)
  let left = 0;
  let right = rows * cols - 1;

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    // 1D-Index zurück in 2D-Koordinaten umwandeln
    const midValue = matrix[Math.floor(mid / cols)][mid % cols];

    if (midValue === target) {
      return true;
    } else if (midValue < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return false;
}

[!TIP] Virtueller Array-Trick: Wenn eine 2D-Matrix vollständig sortiert ist (wie in diesem Fall), suchen Sie nicht Zeile für Zeile. Behandeln Sie sie als “virtuelles” 1D-Array. Der Index i wird auf matrix[Math.floor(i / cols)][i % cols] abgebildet.

Checkliste für Suchbedingungen

Wenn Sie sich fragen, ob Sie die Binäre Suche verwenden können, fragen Sie sich:

• Sind die Daten sortiert?
• Kann ich den Suchraum basierend auf einem mittleren Element halbieren?
• Kann ich eine obere oder untere Schranke finden?

Effizienz-Tipp für Interviews

Wenn die Daten nicht sortiert sind, dauert das Sortieren normalerweise $O(n \log n)$ und die anschließende binäre Suche $O(\log n)$. Gesamt: $O(n \log n)$. Wenn Sie nur einmal suchen, ist eine einfache $O(n)$-Suche tatsächlich schneller! Verwenden Sie die Binäre Suche auf unsortierten Daten nur, wenn Sie planen, mehrmals zu suchen.