Binäre Suche

Nehmen wir an, dass wir Personen suchen wollen und haben unsere Datensätze von Personen in folgender Struktur gespeichert:

struct Person
{
  char * Firstname;
  char * Name;
};

Nun gibt es ein Array von Personen:

struct Person[] = 
{ { "Anton", "Ansbach" }      // 0
, { "Berta", "Block" }        // 1
, { "Caspar", "Cornelius" }   // 2
, { "Dorothea", "Dünnwald" }  // 3
, { "Ernst", "Esbach" }       // 4
, { "Frank", "Ferdinand" }    // 5
, { "Günny", "Grass" }        // 6
, { "Harald", "Hüsch" }       // 7
, { "Ingo", "Isepeter" }      // 8
, { "Jürgen", "Jablonsky" }   // 9
, { "Karl", "Klaasen" }       // 10
, { "Lothar", "Lombatz" }     // 11
, { "Martha", "Moritz" }      // 12
, { "Norbert", "Nöltgen" }    // 13
, { "Otto", "Ottendorf" }     // 14
, { "Peter", "Pech" }         // 15
, { "Quintin", "Quandt" }     // 16
, { "Richard", "Rosenthal" }  // 17
, { "Simone", "Simpson" }     // 18
, { "Thorsten", "Torf" }      // 19
, { "Ursus", "Unkelbach" }    // 20
, { "Viktor", "Vogel" }       // 21
, { "Walter", "Wurz" }        // 22
, { "Xaver", "Xbeliebig" }    // 23
, { "Yan", "Yacht" }          // 24
, { "Zelda", "Zett" }         // 25
, { NULL, NULL }              // 26 - Endmarkierung 
};

Nun stellt sich die Frage, wie man von einem gegebenen Vornamen, den passenden Nachnamen findet. Zunächst gibt es eine einfache Möglichkeit: Man geht Schritt für Schritt durch:

int main( void )
{
  char const * name = "Nöltgen";
  int versuche = 0;
  int position = 0;
 
  while( !strcmp( Personen[ position ], name ) )
  {
    position++;
    versuche++;
  }
 
  if( Personen[ position ].Name == NULL )
    printf( "Name nicht gefunden\n" );
  else
    printf( "'%s' gefunden: Vorname: '%s'\n", name, Personen[ position ].Firstname );
 
  printf( "Um den Namen '%s' zu finden wurden %d Versuche benötigt.\n", name, versuche );
}

Diese Lösung ist einfach zu programmieren, sie findet garantiert die gesuchte Person, sofern sie existiert und sie ist extrem langsam. Stell Dir vor, Du suchst die Telefonnummer von jemandem im Telefonbuch und Du beginnst ab dem ersten Namen jeden einzelnen Namen mit dem gesuchten Namen zu vergleichen.

Überspringen von sortierten Elementen

Daher sind Telefonbücher alphabetisch sortiert und wir Menschen machen uns die Sortierung zu nutze, in dem wir das Telefonbuch mittig aufschlagen und dann die Seiten erst schnell, dann langsamer durch die Finger laufen lassen, bis wir etwa da angekommen sind, wo wir hin müssen. Anschließend gehen wir ein paar Seiten vor oder zurück und finden die gesuchte Person.

Dieses Verfahren ist für Menschen optimal, auch Computer können Abschnitte überspringen, zum Beispiel in dem man solange fünf Namen überspringt, bis man über den gesuchten Namen hinausgesprungen ist und sich anschließend zurückhangelt. Im Fall „Nöltgen“, würde man hier also „Ansbach“ (1. Vergleich), „Ferdinand“ (2.), „Klaasen“ (3.) überspringen und bei „Pech“ (4.) feststellen, dass man zu weit gegangen wäre. Anschließend müsste man sich zurückhangeln, bis man den Namen findet oder zu weit nach vorne gegangen wäre (der gesuchte Name also nicht existiert). Um „Pech“ zu finden, würde man also erst „Ottendorf“ (5.) vergleichen und anschließend „Nöltgen“ (6. Vergleich). Während man beim gradlinigen Durchsuchen in unserem Beispiel 16 Vergleiche benötigt, um „Nöltgen“ zu finden, ist man beim mit dem Überspringen von sortierten Datensätzen bereits nach 6 Vergleichen am Ziel.

Die binäre Suche

Der effektivste Schritt beim Durchsuchen des Telefonbuches war es in der Mitte aufzuschlagen. In dem Moment entscheidet man sich, ob man nach links oder rechts blättert. Man entscheidet sich also, ob man 'Nöltgen' zwischen A-N oder O-Z suchen muss. Nun kann man Vergleichen: Ist der gesuchte Name „Nöltgen“ kleiner oder gleich dem mittleren Element „Nöltgen“ oder ist er später einsortiert. Mit der Entscheidung, dass 'Nöltgen' in A-N liegen muss entscheidet man sich gleichzeitig gegen die Hälfte aller vorhandenen Daten, weil wir uns O-Z gar nicht erst ansehen. Die Anzahl der zu durchsuchenden Daten halbiert sich schlagartig bereits beim 1. Vergleich.