Fachkonzept: Brute-Force- und Lineare Suche

Die Brute-Force-Suche

Sucht man ein bestimmtes Element in einem Array, ist die erste Idee, den Array einfach Schritt für Schritt durchzugehen, bis das Element enweder gefunden wurde, oder eben nicht. Dieses Vorgehen nennt man Brute Force.

Die Anzahl der Operationen ist abhängig von der Position des gesuchten Elements und entspricht im schlimmsten Fall der Länge des Arrays.

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

Die Lineare Suche

Sucht man ein bestimmtes Element in einem sortierten Array, kann man zunächst fast das gleiche Vorgehen verwenden. Wird das Element gefunden, verändert sich die Anzahl der Operationen nicht.

Fügt man eine zusätzliche Abbruchbedingung hinzu, nämlich wenn man ein Element erreicht hat, das größer als das gesuchte Element ist, verringert sich die Anzahl der Operationen allerdings für den Worst Case (das Element wird nicht gefunden) auf die Position des nächstgrößeren Elements im Array.

Nachteil der Linearen Suche ist, dass das Array sortiert sein muss.

Code: Die Brute-Force-Suche

SearchBruteForce.pde

int[] daten = new int[] { 8, 52, 33, 30, 69, 84, 72, 99, 78, 86, 18, 17, 89, 83, 65, 95, 14, 6, 9, 38, 5, 98, 9, 39, 82 };
 
int gesucht = 72;
boolean gefunden = false;
int position = 0;
int anzahlSchritte = 0;
 
while (!gefunden && position < daten.length) {
  anzahlSchritte++;
 
  if (daten[position] == gesucht) {
    gefunden = true;
  } else {
    position++;
  }
}
 
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.");
}

Code: Lineare Suche

SearchLinear.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 = 72;
boolean abbruch = false;
boolean gefunden = false;
int position = 0;
int anzahlSchritte = 0;
 
while (!(abbruch || gefunden) && position < daten.length) {
  anzahlSchritte++;
 
  if (daten[position] == gesucht) {
    gefunden = true;
  } else if (daten[position] > gesucht) {
    abbruch = true;
  } else {
    position++;
  }
}
 
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.");
}