Binäre Suche - LinkFang.de





Binäre Suche


Die binäre Suche ist ein Algorithmus, der auf einem Feld (also meist „in einer Liste“) sehr effizient ein gesuchtes Element findet bzw. eine zuverlässige Aussage über das Fehlen dieses Elementes liefert. Voraussetzung ist, dass die Elemente in dem Feld entsprechend einer totalen Ordnungsrelation angeordnet („sortiert“) sind. Der Algorithmus basiert auf einer einfachen Form des Schemas Teile und Herrsche, zugleich stellt er auch einen Greedy-Algorithmus dar. Ordnung und spätere Suche müssen sich auf denselben Schlüssel beziehen.

Algorithmus

Zuerst wird das mittlere Element des Felds überprüft. Es kann kleiner, größer oder gleich dem gesuchten Element sein. Ist es kleiner als das gesuchte Element, muss das gesuchte Element in der hinteren Hälfte stecken, falls es sich dort überhaupt befindet. Ist es hingegen größer, muss nur in der vorderen Hälfte weitergesucht werden. Die jeweils andere Hälfte muss nicht mehr betrachtet werden. Ist es gleich dem gesuchten Element, ist die Suche beendet.

In der zu untersuchenden Hälfte (und erneut in den folgenden Hälften) wird genauso verfahren: Das mittlere Element liefert wieder die Entscheidung darüber, ob und wo weitergesucht werden muss. Die Länge des Suchbereiches wird so von Schritt zu Schritt halbiert. Spätestens wenn der Suchbereich auf ein einzelnes Element geschrumpft ist, ist die Suche beendet. Dieses eine Element ist entweder das gesuchte Element, oder das gesuchte Element kommt nicht vor.

Der Algorithmus zur binären Suche wird entweder als Iteration oder Rekursion implementiert. Um ihn verwenden zu können, müssen die Daten bereits sortiert und in einer Datenstruktur vorliegen, in der „direkt“ auf das n-te Element zugegriffen werden kann. Auf einer einfachen verketteten Liste würde die Effizienz verloren gehen (siehe aber Skip-Liste).

Komplexität

Um in einem Feld mit [math]n[/math] Einträgen die An- oder Abwesenheit eines Schlüssels festzustellen, werden maximal [math]\lceil \log_2 (n+1) \rceil[/math] Vergleichsschritte benötigt. Somit liegt die binäre Suche, in der Landau-Notation ausgedrückt, in der Komplexitätsklasse [math]\mathcal{O}(\log\ n)[/math]. Damit ist sie deutlich schneller als die lineare Suche, welche allerdings den Vorteil hat, auch in unsortierten Feldern zu funktionieren. In Spezialfällen kann die Interpolationssuche schneller sein als die binäre Suche.

Ähnliche Verfahren und Varianten

Intervallschachtelung

Hauptartikel: Intervallschachtelung

Das hier beschriebene binäre Suchverfahren kann als eine (endliche) Ausprägung der Intervallschachtelung aus der mathematischen Analysis angesehen werden.

Binärer Suchbaum

Hauptartikel: Binärer Suchbaum

Der Such-Algorithmus entspricht auch der Suche in einem binären Suchbaum, wenn man das Array als solchen interpretiert: das mittlere Element ist die Wurzel, die Mitten der so entstehenden Hälften die Wurzeln der entsprechenden Teilbäume und so fort. Der aus dieser Interpretation resultierende Binärbaum ist sogar ein sog. vollständig balancierter Binärbaum, d. i. ein Binärbaum, bei dem die Längen der Pfade von den Blättern zur Wurzel sich um höchstens 1 unterscheiden. Und zwar gilt dies unabhängig von der Richtung der Rundung bei der Bildung des Mittelwerts der Indizes.[1] Der so entstandene Binärbaum ist (wie die binäre Suche) unter allen Binärbäumen mit [math]n[/math] Elementen optimal in Bezug auf

  • die maximale Pfadlänge [math]h:=\lceil \log_2 (n+1) \rceil[/math]   (= Höhe des Baums),
  • die Pfadlängensumme, die sich zu [math]1+(n+1)h-2^h[/math] ergibt, und
  • die mittlere Pfadlänge.

Letztere entspricht der mittleren Anzahl von Vergleichen, wenn alle Elemente gleich wahrscheinlich sind.

Teilt man nicht in der Mitte, so ist das Ergebnis immer noch ein binärer Suchbaum, jedoch ist er u. U. nicht balanciert und nicht optimal.

Die große Überlegenheit des binären Suchbaums gegenüber der binären Suche im Array liegt erstens im besseren Verhalten bei Einfügungen und Löschungen, bei denen im Mittel ein linearer Aufwand anfällt. Bei Bäumen gibt es auch in diesen Fällen Implementierungen mit garantiert logarithmischer Laufzeit. Dort ist auch die Speicherverwaltung einfacher, da Änderungen nicht das ganze Array betreffen, sondern sich mit dem Entstehen oder Verschwinden eines Elementes direkt verbinden lassen. Zweitens können Bäume besser als das Array an Häufigkeiten angepasst werden. Wenn aber das Array schon fertig sortiert ist und sich dann nicht mehr ändert und Zugriffswahrscheinlichkeiten keine Rolle spielen, ist das Array ein gutes Verfahren.

Binäre Suche und totale Quasiordnung

Da das Array als endlicher Definitionsbereich einer Funktion angesehen werden kann, die natürlich nicht notwendigerweise injektiv sein muss, lässt sich das Vorkommen von Duplikaten leicht über die Funktionswerte regeln. Und wenn die Ordnungsrelation von vornherein schon keine Totalordnung, sondern nur eine totale Quasiordnung ist, ist es ggf. sparsamer, die Äquivalenzklassen vor dem Vergleichen zu bilden, als alle möglichen Duplikate im Array zu halten.

Beispiel

In einer Sammlung von Schlüsselwörtern soll zwar Groß- und Kleinschreibung zulässig sein, die Schlüsselwörter sollen sich aber in ihrer Bedeutung nicht unterscheiden.

Interpolationssuche

Hauptartikel: Interpolationssuche

Bei der Interpolationssuche wird das Array nicht mittig geteilt, sondern per linearer Interpolation die Position des gesuchten Elementes abgeschätzt. Sind die Schlüssel in etwa äquidistant verteilt, so kann das gesuchte Element in nahezu konstanter Zeit gefunden werden. In einem ungünstigen Fall wird die Laufzeit jedoch linear. Abgesehen davon muss der Definitionsbereich sich für eine lineare Interpolation eignen.

Quadratische Binärsuche

Hauptartikel: Quadratische Binärsuche

Bei der quadratischen Binärsuche versucht man die Vorteile der Interpolationssuche mit denen der normalen Binärsuche zu kombinieren und mittels Interpolation in jeder Iteration den Suchraum auf ein Intervall der Länge [math]\sqrt n[/math] zu verkleinern.

Verschiedene Implementierungen

In zahlreichen Programmiersprachen ist dieser Algorithmus in den Klassenbibliotheken verfügbar. In Java beispielsweise als java.util.Arrays.binarySearch und java.util.Collections.binarySearch, in Python als das Paket bisect und in C++/STL als std::binary_search im "algorithms" header.

Als Rückgabewert wird die Feldposition zurückgegeben, an der der gesuchte Eintrag gefunden wurde. Konnte der Eintrag nicht gefunden werden, wird meist die Position zurückgegeben, an der er stehen müsste, jedoch z. B. negativ - als Hinweis auf „wurde nicht gefunden“. Nachfolgende Implementierungen geben jedoch in diesem Fall nur "0" oder "-1" zurück („wurde nicht gefunden“).

Bei großen Feldern kann die Berechnung der Mittenposition

 Variable: Mitte = (Links + Rechts) DIV 2 

bei der Addition zu einem Überlauf führen, weshalb oft stattdessen

 Variable: Mitte = Links + ((Rechts - Links) DIV 2) 

implementiert wird.

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung.

C

Beispiel in C (iterativ):

/**
 * Binäre Suche auf dem Array M nach dem Eintrag suchwert
 *
 * @param M :          zu durchsuchendes Feld
 * @param eintraege :  Anzahl der Feldelemente
 * @param suchwert :   gesuchter Eintrag
 * @return >= 0: Index des gesuchten Eintrags
 *         <  0: nichts gefunden
 */
int binary_search(const int M[], const int eintraege, const int suchwert)
{
    const int NICHT_GEFUNDEN = -1 ;
    int mitte;
    int links = 0;                      /* man beginne beim kleinsten Index */
    int rechts = eintraege - 1;         /* Arrays-Index beginnt bei 0 */
 
    /* Solange die zu durchsuchende Menge nicht leer ist */
    while (links <= rechts)
    {
        mitte = links + ((rechts - links) / 2); /* Bereich halbieren */
 
        if (M[mitte] == suchwert)       /* Element suchwert gefunden? */
            return mitte;
        else
            if (M[mitte] > suchwert)
                rechts = mitte - 1;     /* im linken Abschnitt weitersuchen */
            else /* (M[mitte] < suchwert) */
                links = mitte + 1;      /* im rechten Abschnitt weitersuchen */
            /* end if */
        /* end if */
    }
 
    return NICHT_GEFUNDEN;
    // alternativ: return -mitte ; // gute Positionsschaetzung: "nach (-Returnwert) wuerde es hingehoeren"
}

Python

Rekursives Verfahren in Python:

 def binaersuche_rekursiv(werte, gesucht, start, ende):
    if ende < start:
        return 'nicht gefunden'
        # alternativ: return -start # bei (-Returnwert) waere die richtige Einfuege-Position
    mitte = (start + ende)/2
    if werte[mitte] == gesucht:
        return mitte
    elif werte[mitte] < gesucht:
        return binaersuche_rekursiv(werte, gesucht, mitte+1, ende)
    else:
        return binaersuche_rekursiv(werte, gesucht, start, mitte-1)

Haskell

Beispiel in der funktionalen Programmiersprache Haskell (rekursiv):

data SearchResult = NotFound Integer | Found Integer deriving (Eq, Ord, Show)
 
bsearch :: Ord a => a               -- hiernach wird gesucht
                 -> (Integer -> a)  -- zu durchsuchende Folge, monoton
                 -> Integer         -- Indexuntergrenze (einschließlich)
                 -> Integer         -- Indexobergrenze (ausschließlich)
                 -> SearchResult
bsearch dest s lo hi
    | s lo > dest = NotFound lo
    | hi <= lo    = NotFound lo
    | otherwise   = go lo hi
    where
        -- Invarianten: lo < hi, lo ist immer klein genug, hi ist immer zu groß.
        -- Wir suchen den *größten* Index, der klein genug ist.
        go lo hi
            | lo + 1 == hi = if s lo == dest then Found lo else NotFound hi
            | dest < s mid = go lo mid
            | otherwise    = go mid hi
            where mid = (lo+hi)`div`2

Weblinks

Anmerkungen

  1. Bei einer Belegung des Feldes mit [math]n=2^h-1[/math] Einträgen (das entspricht einem vollständigen Binärbaum der Höhe [math]h[/math]) haben alle Halbierungen einen Divisionsrest von 0.

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Binäre Suche (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.