spezielles Suchverfahren in einer geordneten Menge von Datensätzen.

Es sei A eine Menge von Datensätzen, die nach einem bestimmten Schlüssel aufsteigend geordnet vorliegen. Das Prinzip der binären Suche besteht darin, die Menge nicht sequentiell von Anfang bis Ende zu durchlaufen, sondern in der Mitte der Menge mit der Suche zu beginnen. Hat das dort befindliche Element einen höheren Schlüsselwert als das gesuchte, so muß sich das gesuchte Element in der ersten Hälfte der Menge befinden. Hat es einen niedrigeren Schlüsselwert als das gesuchte, so muß sich das gesuchte Element in der zweiten Hälfte der Menge befinden. Je nachdem, in welcher Hälfte der Menge sich nun das gesuchte Element befindet, greift man anschließend auf die Mitte der vorderen Hälfte oder der hinteren Hälfte zu und verfährt entsprechend so lange, bis das gesuchte Element gefunden ist.

Wir illustrieren das Verfahren anhand der Suche nach einem Element k in einem linear geordneten Bereich A = {α₁,…,α_n}. Zur Beschreibung nehmen wir ohne Einschränkung der Allgemeinheit an, daß A aufsteigend sortiert ist. Um festzustellen, ob es ein i mit a_i = k gibt, wird k mit dem Element \({\alpha }_{m}={\alpha }_{\frac{n}{2}}\) (n gerade) bzw. \({\alpha }_{m}={\alpha }_{\frac{n+1}{2}}\) (n ungerade) verglichen. Falls k = α_m ist, endet die Suche erfolgreich. Ist k< a_m, wird das Verfahren für k und

\begin{eqnarray}{A}_{\gt }=\{{\alpha }_{m+1},\ldots ,{\alpha }_{n}\}\end{eqnarray}

\begin{eqnarray}{A}_{\lt }=\{{\alpha }_{1},\ldots {\alpha }_{m-1}\}\end{eqnarray}

A muß in einer Datenstruktur vorliegen, die unmittelbaren Zugriff auf jedes Element über seinen Index erlaubt.

Das Verfahren der binären Suche setzt voraus, daß die Anzahl der gegebenen Datensätze eine Zweierpotenz ist, da nur in diesem Fall die fortgesetzte Halbierung immer zum Erfolg führen kann. Besteht die Menge aus m = 2ⁿ Elementen, so braucht man zur Suche maximal n = log₂m Schritte.

[1] Drechsler, R.; Becker, B.: Binary Decision Diagrams: Theory and Implementation. Kluwer Academic Publishers Boston Dordrecht London, 1998.
[2] Drechsler, R.; Becker, B.: Graphenbasierte Funktionsdarstellung. B.G. Teubner Stuttgart, 1998.
[3] Molitor, P.; Scholl, Chr.: Datenstrukturen und Effiziente Algorithmen für die Logiksynthese kombinatorischer Schaltungen. B.G. Teubner Stuttgart/Leipzig, 1999.