ALGORITHMUS-LESENOTIZ

Binary Search

Binary search finds a target in a sorted search space by repeatedly discarding half of the remaining range.

TYPAlgorithmusKATEGORIESearchTIEFEEinsteigerTYPISCHE KOMPLEXITÄTO(log n)

KURZE INTERVIEWANTWORT

Beginne mit diesem mentalen Modell

Binary search finds a target in a sorted search space by repeatedly discarding half of the remaining range.

EINFACHE ERKLÄRUNG

So funktioniert es – ohne unnötigen Jargon

Compare target with the middle element.

If target is smaller, continue in the left half; if larger, continue in the right half.

AUSFÜHRUNG

Lies den Algorithmus als Folge von Entscheidungen

Set left and right bounds.

Compute mid without leaving the range.

Move exactly one bound after each comparison until found or left > right.

Ein kleines Beispiel als Orientierung

Searching 23 in [3, 8, 12, 23, 31, 44] checks the middle, then keeps only the half where 23 can still exist.

LESBARE JAVASCRIPT-IMPLEMENTIERUNGJavaScript

function binarySearch(items, target) {
  let left = 0;
  let right = items.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (items[mid] === target) return mid;
    if (items[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

So liest du diesen Code

Lerne die Syntax nicht auswendig. Folge dem Zustand, der sich in jeder Zeile ändert, und verbinde ihn mit der oben beschriebenen Invariante.

KOMPLEXITÄT

O(log n)

Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.

WANN EINSETZEN

Gut geeignet

Match the algorithm to the structure and preprocessing state of the data.

HÄUFIGE FEHLER

Was typischerweise schiefgeht

Using it on unsorted data.
Off-by-one errors and infinite loops.
Not defining whether boundaries are inclusive or half-open.

SO ERKLÄRST DU ES IM INTERVIEW

Struktur einer professionellen Antwort

Say the invariant: if the target exists, it is inside the current search interval. Then explain how each comparison preserves that invariant while halving the interval.

Problem→Kernidee→Invariante / Zustand→Big-O→Trade-off

SCHNELLER INTERVIEW-CHECK

What problem does Binary Search solve?

Binary search finds a target in a sorted search space by repeatedly discarding half of the remaining range.

Was sollte ich zur Komplexität erwähnen?

Its typical cost here is O(log n), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.

Was ist der häufigste Fehler?

Using it on unsorted data.

WeiterlesenSorted arraysLower/upper boundBinary search on answer

function binarySearch(items, target) { let left = 0; let right = items.length - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (items[mid] === target) return mid; if (items[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }