Suchen: lineare und binäre Suche

Um einen Namen in einer sortierten Liste mit einer Million Einträgen zu finden, braucht die binäre Suche nie mehr als 20 Prüfungen.

Einen Wert suchen

Suchen ist das Problem, herauszufinden, wo ein Wert in einer Sammlung steht, oder zu erfahren, dass er nicht da ist. Dein Handy tut das, wenn du den Namen eines Kontakts eintippst, ein Laden, wenn er prüft, ob ein Artikel vorrätig ist, und eine Rechtschreibprüfung bei jedem Wort, das du tippst. Die Eingabe ist eine Liste und ein Zielwert. Die Ausgabe ist die Position des Ziels oder ein Zeichen wie -1 für „nicht gefunden“.

Lineare Suche: einer nach dem anderen

Das einfachste Verfahren beginnt links und prüft einen Wert nach dem anderen, bis es das Ziel findet oder die Liste zu Ende ist. Das ist die lineare Suche. Sie funktioniert mit jeder Liste, ob sortiert oder nicht. Ihr Aufwand hängt vom Glück ab: Steht das Ziel vorn, reicht eine Prüfung. Steht es hinten oder fehlt es, prüfst du jeden Wert. Bei einer Liste mit n Werten sind es im schlechtesten Fall n Prüfungen. Eine doppelt so lange Liste kann doppelt so viele Prüfungen brauchen, daher der Name „linear“: Die Arbeit wächst geradlinig mit der Größe.

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return i;  // gefunden
  }
  return -1;                             // alles geprüft
}

Binäre Suche: den Rest halbieren

Ist die Liste sortiert, geht es viel besser. Denk an das Zahlenratespiel: Jemand wählt eine Zahl von 1 bis 100 und antwortet nur „höher“ oder „tiefer“. Wer klug spielt, rät zuerst 50. Egal wie die Antwort lautet, die Hälfte der Möglichkeiten ist weg. Der nächste Tipp ist die Mitte dessen, was übrig ist, und so weiter. Genau das macht die binäre Suche mit einer sortierten Liste. Sie hält zwei Marken, lo und hi, um den Teil, in dem das Ziel noch sein kann. Sie prüft den mittleren Wert. Ist das das Ziel, ist sie fertig. Ist der mittlere Wert kleiner als das Ziel, ist auch alles links davon kleiner, also rückt lo hinter die Mitte. Ist er größer, rückt hi vor die Mitte. Wenn lo an hi vorbeizieht, bleibt nichts übrig, und das Ziel ist nicht in der Liste.

function binarySearch(list, target) {
  let lo = 0, hi = list.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (list[mid] === target) return mid;
    if (list[mid] < target) lo = mid + 1;  // Ziel liegt rechts
    else hi = mid - 1;                     // Ziel liegt links
  }
  return -1;
}

Wie viele Prüfungen?

Jede Prüfung der binären Suche halbiert den übrigen Teil mindestens. Von n Werten bleiben nach einer Prüfung höchstens etwa n/2, nach zwei etwa n/4 und so weiter, bis ein Wert übrig ist. Wie oft man halbieren muss, um von n auf 1 zu kommen, ist der Logarithmus von n zur Basis 2, geschrieben log₂ n. Zählt man die letzte Prüfung mit, braucht die binäre Suche höchstens ⌊log₂ n⌋ + 1 Prüfungen, wobei ⌊ ⌋ Abrunden bedeutet. Bei 100 Werten sind das 7 Prüfungen, deshalb lässt sich das Ratespiel immer mit 7 Tipps gewinnen. Bei 1000 Werten sind es 10, bei einer Million 20 und bei einer Milliarde 30.

Der Haken: Die Liste muss sortiert sein

Die binäre Suche funktioniert nur, weil in einer sortierten Liste ein einziger Vergleich verrät, auf welcher Seite das Ziel liegen muss. In einer unsortierten Liste sagt der mittlere Wert nichts über seine Nachbarn, und du bist wieder bei der linearen Suche. Sortieren kostet selbst Arbeit (darum geht es in den nächsten beiden Einheiten), also hängt die Wahl vom Einsatz ab. Durchsuchst du eine Liste einmal, ist die lineare Suche vielleicht am billigsten. Durchsuchst du dieselbe Liste tausendmal, lohnt es sich schnell, sie einmal zu sortieren und dann binär zu suchen. Dieser Tausch zwischen dem Vorbereiten von Daten und dem Beantworten von Fragen dazu zieht sich durch das ganze Fach.