Fachkonzept: Binäre Suche

Die Binäre Suche

Ein noch besserer Suchalgorithmus auf einem sortierten Array ist die Binäre Suche. Diese basiert auf der Idee, sich zunächst das mittlere Element des zu durchsuchenden Arrays anzuschauen und dann zu entscheiden:

Hat man das gesuchte Element gefunden, ist man fertig.
Ist das gesuchte Element kleiner als das mittlere, verkleinert man den Suchbereich auf die linke Hälfte.
Ist das gesuchte Element größer als das mittlere, verkleintert man den Suchbereich auf die rechte Hälfte.

Mit diesem Vorgehen halbiert man die Länge des zu durchsuchenden Bereichs mit jedem Schritt. Die Anzahl der Operationen ist also $\log_2{n}$, wobei $n$ der Länge des Arrays entspricht.

Vorteil der Brute-Force-Suche ist, dass das Array nicht sortiert sein muss.

Code: Die Binäre Suche

SearchBinary.pde

int[] daten = new int[] { 5, 6, 8, 9, 9, 14, 17, 18, 30, 33, 38, 39, 52, 65, 69, 72, 78, 82, 83, 84, 86, 89, 95, 98, 99 };
 
int gesucht = 118;
int linkeGrenze = 0;
int rechteGrenze = daten.length - 1;
boolean gefunden = false;
int position = -1;
int anzahlSchritte = 0;
 
while (!gefunden && rechteGrenze >= linkeGrenze) {
  anzahlSchritte++;
 
  int pivotIndex = linkeGrenze + (rechteGrenze - linkeGrenze) / 2;
  int pivotElement = daten[pivotIndex];
 
  if (gesucht < pivotElement) {
    rechteGrenze = pivotIndex - 1;
  } else if (gesucht > pivotElement) {
    linkeGrenze = pivotIndex + 1;
  } else {
    gefunden = true;
    position = pivotIndex;
  }
}
 
if (!gefunden) {
  println("Das Element " + gesucht + " wurde nicht gefunden. Abbruch nach " + anzahlSchritte + " Schritten.");
} else {
  println("Die Position von " + gesucht + " ist: " + position + ". Abbruch nach " + anzahlSchritte + " Schritten.");
}