Eine binäre Suche, auch bekannt als Halbintervallsuche, ist ein Algorithmus, der in der Informatik verwendet wird, um einen bestimmten Wert (Schlüssel) innerhalb eines Arrays zu finden. Damit die Suche binär ist, muss das Array entweder in aufsteigender oder absteigender Reihenfolge sortiert werden.
Wie funktioniert es?
Wie Sie im Diagramm sehen können, wird bei jedem Schritt des Algorithmus ein Vergleich durchgeführt. Dann verzweigt sich die Prozedur in eine von zwei Richtungen. Insbesondere wird der Schlüsselwert mit dem mittleren Element des Arrays verglichen. Wenn der Schlüsselwert kleiner oder größer als dieses mittlere Element ist, weiß der Algorithmus, welche Hälfte des Arrays mit der Suche fortfahren soll. Der Grund ist, dass das Array sortiert ist. Dieser Vorgang wird für immer kleinere Segmente des Arrays wiederholt, bis der Wert lokalisiert ist.
Da jeder Schritt im Algorithmus die Arraygröße halbiert, wird eine binäre Suche in logarithmischer Zeit erfolgreich abgeschlossen. Das heißt, das Worst-Case-Szenario für ein Array aus n Elementen liegt garantiert innerhalb von log(n)-Operationen.
Binär, Programmierbegriffe, Suche
