Direkt zum Inhalt

Lexikon der Mathematik: binäre Suche

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 = {α1,…,αn}. Zur Beschreibung nehmen wir ohne Einschränkung der Allgemeinheit an, daß A aufsteigend sortiert ist. Um festzustellen, ob es ein i mit ai = 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 < am, wird das Verfahren für k und

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

wiederholt. Ist k < am, wird das Verfahren für k und

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

wiederholt. Die Suche endet erfolglos, falls der Restbereich leer ist.

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 = 2n Elementen, so braucht man zur Suche maximal n = log2m 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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos