binäre Suche

1. Begriff: bekannter Algorithmus für das Suchen.

2. Voraussetzung: Der zu durchsuchende Datenbestand ist nach dem Suchbegriff geordnet, d.h. aufsteigend (oder absteigend) sortiert.

3. Prinzip: fortgesetzte Intervallhalbierung; der Datenbestand wird zunächst in der Mitte überprüft. Wenn die mittlere Komponente nicht zufällig die gesuchte ist, muss die gesuchte Komponente entweder im „linken” Teil liegen (nämlich dann, wenn bei aufsteigender Sortierung der Suchbegriff kleiner als der Ordnungsbegriff der mittleren Komponente ist) oder im „rechten” Teil (im umgekehrten Fall). Auf das entsprechende Teilintervall wird die gleiche Vorgehensweise analog angewendet etc.

4. Umsetzung: für die binäre Suche existiert eine elegante Lösung mit rekursiver Programmierung.