Binärer Suchalgorithmus - Binary search algorithm

Binärer Suchalgorithmus
Binäre Suche Darstellung.svg
Visualisierung des binären Suchalgorithmus, wobei 7 der Zielwert ist
Klasse Suchalgorithmus
Datenstruktur Array
Worst-Case- Leistung O (log n )
Best-Case- Leistung O (1)
Durchschnittliche Leistung O (log n )
Raumkomplexität im schlimmsten Fall O (1)

In der Informatik ist die binäre Suche , auch bekannt als Halbintervallsuche , logarithmische Suche oder binäres Chop , ein Suchalgorithmus , der die Position eines Zielwerts innerhalb eines sortierten Arrays findet . Die binäre Suche vergleicht den Zielwert mit dem mittleren Element des Arrays. Wenn sie nicht gleich sind, wird die Hälfte eliminiert, in der das Ziel nicht liegen kann, und die Suche wird auf der verbleibenden Hälfte fortgesetzt, wobei wiederum das mittlere Element zum Vergleich mit dem Zielwert genommen wird und dies wiederholt wird, bis der Zielwert gefunden ist. Wenn die Suche damit endet, dass die verbleibende Hälfte leer ist, befindet sich das Ziel nicht im Array.

Binäre Suchläufe in logarithmischer Zeit im schlimmsten Fall , so dass Vergleiche, in denen die Anzahl der Elemente im Array ist. Die binäre Suche ist mit Ausnahme kleiner Arrays schneller als die lineare Suche . Das Array muss jedoch zuerst sortiert werden, um die binäre Suche anwenden zu können. Es gibt spezialisierte Datenstrukturen, die für eine schnelle Suche entwickelt wurden, wie beispielsweise Hash-Tabellen , die effizienter durchsucht werden können als die binäre Suche. Die binäre Suche kann jedoch verwendet werden, um eine breitere Palette von Problemen zu lösen, wie z. B. das Finden des nächstkleineren oder nächstgrößeren Elements im Array relativ zum Ziel, selbst wenn es im Array nicht vorhanden ist.

Es gibt zahlreiche Varianten der binären Suche. Insbesondere beschleunigt die fraktionale Kaskadierung die binäre Suche nach demselben Wert in mehreren Arrays. Die fraktionierte Kaskadierung löst effizient eine Reihe von Suchproblemen in der Computergeometrie und in zahlreichen anderen Gebieten. Die exponentielle Suche erweitert die binäre Suche auf unbegrenzte Listen. Der binäre Suchbaum und die B-Baum- Datenstrukturen basieren auf der binären Suche.

Algorithmus

Die binäre Suche funktioniert bei sortierten Arrays. Die binäre Suche beginnt mit dem Vergleich eines Elements in der Mitte des Arrays mit dem Zielwert. Wenn der Zielwert mit dem Element übereinstimmt, wird seine Position im Array zurückgegeben. Ist der Zielwert kleiner als das Element, wird die Suche in der unteren Hälfte des Arrays fortgesetzt. Ist der Zielwert größer als das Element, wird die Suche in der oberen Hälfte des Arrays fortgesetzt. Dadurch eliminiert der Algorithmus in jeder Iteration die Hälfte, in der der Zielwert nicht liegen kann.

Verfahren

Bei einem Array von Elementen mit Werten oder Datensätzen, die so sortiert sind, dass , und Zielwert , verwendet die folgende Subroutine die binäre Suche, um den Index von in zu finden .

  1. Stellen Sie auf und auf ein .
  2. Wenn , wird die Suche als erfolglos beendet.
  3. Setzt (die Position des mittleren Elements) auf den Boden von , der die größte ganze Zahl kleiner oder gleich ist .
  4. Wenn , stellen Sie auf und gehen Sie zu Schritt 2.
  5. Wenn , stellen Sie auf und gehen Sie zu Schritt 2.
  6. Jetzt ist die Suche abgeschlossen; zurück .

Dieses iterative Verfahren verfolgt die Suchgrenzen mit den beiden Variablen und . Die Prozedur kann wie folgt in Pseudocode ausgedrückt werden, wobei die Variablennamen und -typen die gleichen wie oben bleiben, die Floor-Funktion ist und sich auf einen bestimmten Wert bezieht, der das Fehlschlagen der Suche anzeigt. floorunsuccessful

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

Alternativ kann der Algorithmus die Obergrenze von annehmen . Dies kann das Ergebnis ändern, wenn der Zielwert mehr als einmal im Array vorkommt.

Alternatives Verfahren

Bei der obigen Prozedur prüft der Algorithmus in jeder Iteration , ob das mittlere Element ( ) gleich dem Ziel ( ) ist. Einige Implementierungen lassen diese Prüfung während jeder Iteration aus. Der Algorithmus würde diese Prüfung nur durchführen, wenn ein Element übrig ist (when ). Dies führt zu einer schnelleren Vergleichsschleife, da pro Iteration ein Vergleich eliminiert wird. Im Durchschnitt ist jedoch eine weitere Iteration erforderlich.

Hermann Bottenbruch veröffentlichte 1962 die erste Implementierung, bei der dieser Scheck weggelassen wurde.

  1. Stellen Sie auf und auf ein .
  2. Während ,
    1. Legen Sie (die Position des mittleren Elements) auf die Obergrenze von fest , die die kleinste ganze Zahl größer oder gleich ist .
    2. Wenn , setzen Sie auf .
    3. Sonst, ; gesetzt zu .
  3. Nun ist die Suche abgeschlossen. Wenn , zurück . Andernfalls wird die Suche als erfolglos beendet.

Wo ceilist die Deckenfunktion, der Pseudocode für diese Version ist:

function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] > T then
            R := m − 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

Doppelte Elemente

Die Prozedur kann jeden Index zurückgeben, dessen Element dem Zielwert entspricht, selbst wenn das Array doppelte Elemente enthält. Wenn beispielsweise das zu durchsuchende Array und das Ziel lautete , wäre es für den Algorithmus richtig, entweder das 4. (Index 3) oder das 5. (Index 4) Element zurückzugeben. Das reguläre Verfahren würde in diesem Fall das 4. Element (Index 3) zurückgeben. Es gibt nicht immer das erste Duplikat zurück (bedenken Sie, welches immer noch das vierte Element zurückgibt). Es ist jedoch manchmal erforderlich, das Element ganz links oder ganz rechts für einen Zielwert zu finden, der im Array dupliziert wird. Im obigen Beispiel ist das 4. Element das am weitesten links stehende Element des Werts 4, während das 5. Element das am weitesten rechts liegende Element des Werts 4 ist. Das obige alternative Verfahren gibt immer den Index des am weitesten rechts stehenden Elements zurück, wenn ein solches Element vorhanden ist.

Vorgehensweise zum Finden des Elements ganz links

Um das Element ganz links zu finden, kann das folgende Verfahren verwendet werden:

  1. Stellen Sie auf und auf ein .
  2. Während ,
    1. Setzt (die Position des mittleren Elements) auf den Boden von , der die größte ganze Zahl kleiner oder gleich ist .
    2. Wenn , setzen Sie auf .
    3. Sonst, ; gesetzt zu .
  3. Zurück .

Wenn und , dann ist das Element ganz links gleich . Auch wenn nicht im Array enthalten ist, ist der Rang von im Array oder die Anzahl der Elemente im Array, die kleiner als sind .

Wo floorist die Floor-Funktion, der Pseudocode für diese Version ist:

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

Vorgehensweise zum Finden des Elements ganz rechts

Um das äußerst rechte Element zu finden, kann das folgende Verfahren verwendet werden:

  1. Stellen Sie auf und auf ein .
  2. Während ,
    1. Setzt (die Position des mittleren Elements) auf den Boden von , der die größte ganze Zahl kleiner oder gleich ist .
    2. Wenn , setzen Sie auf .
    3. Sonst, ; gesetzt zu .
  3. Zurück .

Wenn und , dann ist das Element ganz rechts gleich . Auch wenn nicht im Array enthalten ist, ist die Anzahl der Elemente im Array größer als .

Wo floorist die Floor-Funktion, der Pseudocode für diese Version ist:

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

Ungefähre Übereinstimmungen

Die binäre Suche kann angepasst werden, um ungefähre Übereinstimmungen zu berechnen. Im obigen Beispiel werden Rang, Vorgänger, Nachfolger und nächster Nachbar für den Zielwert angezeigt , der sich nicht im Array befindet.

Das obige Verfahren führt nur genaue Übereinstimmungen durch und findet die Position eines Zielwerts. Es ist jedoch trivial, die binäre Suche zu erweitern, um ungefähre Übereinstimmungen durchzuführen, da die binäre Suche mit sortierten Arrays arbeitet. Beispielsweise kann die binäre Suche verwendet werden, um für einen bestimmten Wert seinen Rang (die Anzahl der kleineren Elemente), den Vorgänger (nächstkleinstes Element), Nachfolger (nächstgrößtes Element) und den nächsten Nachbarn zu berechnen . Bereichsabfragen, die die Anzahl der Elemente zwischen zwei Werten suchen, können mit zwei Rangabfragen durchgeführt werden.

  • Rangabfragen können mit dem Verfahren zum Auffinden des Elements ganz links durchgeführt werden . Die Anzahl der Elemente, die kleiner als der Zielwert sind, wird von der Prozedur zurückgegeben.
  • Vorgängerabfragen können mit Rangabfragen durchgeführt werden. Wenn der Zielwert den Rang hat, ist sein Vorgänger  .
  • Für Folgeabfragen kann das Verfahren zum Auffinden des ganz rechten Elements verwendet werden. Wenn das Ergebnis der Ausführung der Prozedur für den Zielwert lautet , dann ist der Nachfolger des Zielwerts  .
  • Der nächste Nachbar des Zielwerts ist entweder sein Vorgänger oder Nachfolger, je nachdem, welcher Wert näher liegt.
  • Bereichsabfragen sind ebenfalls unkompliziert. Sobald die Ränge der beiden Werte bekannt sind, ist die Anzahl der Elemente größer oder gleich dem ersten Wert und kleiner als der zweite die Differenz der beiden Ränge. Diese Anzahl kann um eins nach oben oder unten angepasst werden, je nachdem, ob die Endpunkte des Bereichs als Teil des Bereichs betrachtet werden sollen und ob das Array Einträge enthält, die diesen Endpunkten entsprechen.

Leistung

Ein Baum, der die binäre Suche darstellt. Das hier durchsuchte Array ist , und der Zielwert ist .
Der schlechteste Fall wird erreicht, wenn die Suche die tiefste Ebene des Baums erreicht, während der beste Fall erreicht wird, wenn der Zielwert das mittlere Element ist.

Hinsichtlich der Anzahl von Vergleichen kann die Leistung der binären Suche analysiert werden, indem der Ablauf der Prozedur in einem binären Baum betrachtet wird. Der Wurzelknoten des Baums ist das mittlere Element des Arrays. Das mittlere Element der unteren Hälfte ist der linke untergeordnete Knoten der Wurzel und das mittlere Element der oberen Hälfte ist der rechte untergeordnete Knoten der Wurzel. Der Rest des Baumes ist in ähnlicher Weise aufgebaut. Ausgehend vom Wurzelknoten werden die linken oder rechten Teilbäume durchlaufen, je nachdem ob der Zielwert kleiner oder größer als der betrachtete Knoten ist.

Im schlimmsten Fall macht Binärsuche Iterationen der Vergleichs - Schleife, wobei die Notation die bezeichneten Bodenfunktion , die die größte ganze Zahl kleiner als oder gleich das Argument ist , und liefert der binäre Logarithmus . Dies liegt daran, dass der schlimmste Fall erreicht wird, wenn die Suche die tiefste Ebene des Baums erreicht und es immer Ebenen im Baum für jede binäre Suche gibt.

Der schlimmste Fall kann auch erreicht werden, wenn sich das Zielelement nicht im Array befindet. Wenn eins kleiner als eine Zweierpotenz ist, ist dies immer der Fall. Andernfalls kann die Suche Iterationen durchführen, wenn die Suche die tiefste Ebene des Baums erreicht. Es kann jedoch Iterationen machen , die eine weniger als im schlimmsten Fall sind, wenn die Suche auf der zweittiefsten Ebene des Baums endet.

Unter der Annahme, dass jedes Element mit gleicher Wahrscheinlichkeit durchsucht wird, führt die binäre Suche im Durchschnitt Iterationen durch, wenn sich das Zielelement im Array befindet. Dies entspricht ungefähr den Iterationen. Wenn sich das Zielelement nicht im Array befindet, führt die binäre Suche im Durchschnitt Iterationen durch, wobei davon ausgegangen wird, dass der Bereich zwischen und außerhalb der Elemente mit gleicher Wahrscheinlichkeit durchsucht wird.

Im besten Fall, wenn der Zielwert das mittlere Element des Arrays ist, wird seine Position nach einer Iteration zurückgegeben.

In Bezug auf Iterationen kann kein Suchalgorithmus, der nur durch den Vergleich von Elementen funktioniert, eine bessere Durchschnitts- und Worst-Case-Leistung aufweisen als die binäre Suche. Der Vergleichsbaum, der die binäre Suche repräsentiert, hat die geringstmöglichen Ebenen, da jede Ebene über der untersten Ebene des Baums vollständig gefüllt ist. Andernfalls kann der Suchalgorithmus wenige Elemente in einer Iteration eliminieren, wodurch die Anzahl der im Durchschnitt und im schlimmsten Fall erforderlichen Iterationen erhöht wird. Dies ist bei anderen Suchalgorithmen der Fall, die auf Vergleichen basieren, da sie zwar bei einigen Zielwerten schneller arbeiten, die durchschnittliche Leistung über alle Elemente jedoch schlechter ist als bei der binären Suche. Durch die Halbierung des Arrays stellt die binäre Suche sicher, dass die Größe beider Teilarrays so ähnlich wie möglich ist.

Raumkomplexität

Die binäre Suche erfordert drei Zeiger auf Elemente, die Array-Indizes oder Zeiger auf Speicherorte sein können, unabhängig von der Größe des Arrays. Daher liegt die Raumkomplexität der binären Suche im Wort-RAM- Berechnungsmodell.

Herleitung des Durchschnittsfalls

Die durchschnittliche Anzahl von Iterationen, die durch die binäre Suche durchgeführt werden, hängt von der Wahrscheinlichkeit jedes gesuchten Elements ab. Der durchschnittliche Fall unterscheidet sich bei erfolgreichen Suchen und erfolglosen Suchen. Es wird angenommen, dass jedes Element mit gleicher Wahrscheinlichkeit nach erfolgreichen Suchen durchsucht wird. Bei erfolglosen Suchen wird angenommen, dass die Intervalle zwischen und außerhalb von Elementen mit gleicher Wahrscheinlichkeit durchsucht werden. Der durchschnittliche Fall für erfolgreiche Suchen ist die Anzahl der Iterationen, die erforderlich ist, um jedes Element genau einmal zu durchsuchen, geteilt durch die Anzahl der Elemente. Der durchschnittliche Fall für erfolglose Suchen ist die Anzahl der Iterationen, die erforderlich ist, um ein Element innerhalb jedes Intervalls genau einmal zu durchsuchen, dividiert durch die Intervalle.

Erfolgreiche Suche

In der binären Baumdarstellung kann eine erfolgreiche Suche durch einen Pfad von der Wurzel zum Zielknoten dargestellt werden, der als interner Pfad bezeichnet wird . Die Länge eines Pfades ist die Anzahl der Kanten (Verbindungen zwischen Knoten), die der Pfad durchquert. Die Anzahl der von einer Suche durchgeführten Iterationen, vorausgesetzt, der entsprechende Pfad hat die Länge , zählt die anfängliche Iteration. Die interne Pfadlänge ist die Summe der Längen aller eindeutigen internen Pfade. Da es nur einen Pfad von der Wurzel zu jedem einzelnen Knoten gibt, repräsentiert jeder interne Pfad eine Suche nach einem bestimmten Element. Wenn Elemente vorhanden sind , die eine positive ganze Zahl sind und die interne Pfadlänge ist , dann die durchschnittliche Anzahl von Iterationen für eine erfolgreiche Suche , wobei die eine Iteration hinzugefügt wird, um die anfängliche Iteration zu zählen.

Da die binäre Suche der optimale Algorithmus für die Suche mit Vergleichen ist, reduziert sich dieses Problem auf die Berechnung der minimalen internen Pfadlänge aller binären Bäume mit Knoten, die gleich ist:

In einem Array mit 7 Elementen erfordert beispielsweise die Wurzel eine Iteration, die beiden Elemente unterhalb der Wurzel zwei Iterationen und die vier Elemente darunter drei Iterationen. In diesem Fall beträgt die interne Pfadlänge:

Die durchschnittliche Anzahl von Iterationen würde auf der Gleichung für den durchschnittlichen Fall basieren. Die Summe für kann vereinfacht werden zu:

Einsetzen der Gleichung für in die Gleichung für :

Für integer entspricht dies der oben angegebenen Gleichung für den durchschnittlichen Fall bei einer erfolgreichen Suche.

Erfolglose Suche

Nicht erfolgreiche Suchen können dargestellt werden, indem der Baum mit externen Knoten erweitert wird , was einen erweiterten Binärbaum bildet . Wenn ein interner Knoten oder ein im Baum vorhandener Knoten weniger als zwei untergeordnete Knoten hat, werden zusätzliche untergeordnete Knoten, sogenannte externe Knoten, hinzugefügt, sodass jeder interne Knoten zwei untergeordnete Knoten hat. Auf diese Weise kann eine erfolglose Suche als Pfad zu einem externen Knoten dargestellt werden, dessen Eltern das einzige Element ist, das während der letzten Iteration verbleibt. Ein externer Pfad ist ein Pfad von der Wurzel zu einem externen Knoten. Die externe Pfadlänge ist die Summe der Längen aller eindeutigen externen Pfade. Wenn Elemente vorhanden sind , was eine positive ganze Zahl ist und die externe Pfadlänge ist , dann die durchschnittliche Anzahl von Iterationen für eine erfolglose Suche , wobei die eine Iteration hinzugefügt wird, um die anfängliche Iteration zu zählen. Die externe Pfadlänge wird durch statt geteilt, da externe Pfade vorhanden sind , die die Intervalle zwischen und außerhalb der Elemente des Arrays darstellen.

Dieses Problem kann in ähnlicher Weise auf die Bestimmung der minimalen externen Pfadlänge aller Binärbäume mit Knoten reduziert werden. Für alle binären Bäume ist die externe Pfadlänge gleich der internen Pfadlänge plus . Ersetzen der Gleichung für :

Durch Einsetzen der Gleichung für in die Gleichung für kann der durchschnittliche Fall für erfolglose Suchen bestimmt werden:

Durchführung des Alternativverfahrens

Jede Iteration der oben definierten binären Suchprozedur führt einen oder zwei Vergleiche durch, wobei überprüft wird, ob das mittlere Element in jeder Iteration gleich dem Ziel ist. Unter der Annahme, dass jedes Element mit gleicher Wahrscheinlichkeit durchsucht wird, führt jede Iteration im Durchschnitt 1,5 Vergleiche durch. Eine Variante des Algorithmus prüft, ob das mittlere Element am Ende der Suche gleich dem Ziel ist. Dadurch entfällt im Durchschnitt ein halber Vergleich aus jeder Iteration. Dies verkürzt die Zeit pro Iteration auf den meisten Computern geringfügig. Es garantiert jedoch, dass die Suche die maximale Anzahl von Iterationen erfordert, indem durchschnittlich eine Iteration zur Suche hinzugefügt wird. Da die Vergleichsschleife im schlimmsten Fall nur einmal ausgeführt wird, kompensiert die leichte Effizienzsteigerung pro Iteration nicht die zusätzliche Iteration für alle außer sehr großen .

Laufzeit und Cache-Nutzung

Bei der Analyse der Leistung der binären Suche ist eine weitere Überlegung die Zeit, die zum Vergleichen zweier Elemente erforderlich ist. Bei ganzen Zahlen und Strings nimmt die benötigte Zeit linear zu, wenn die Codierungslänge (normalerweise die Anzahl der Bits ) der Elemente zunimmt. Zum Beispiel würde das Vergleichen eines Paares von 64-Bit-Ganzzahlen ohne Vorzeichen einen Vergleich von bis zu doppelt so vielen Bits erfordern, wie ein Paar von 32-Bit-Ganzzahlen ohne Vorzeichen. Der schlimmste Fall wird erreicht, wenn die ganzen Zahlen gleich sind. Dies kann von Bedeutung sein, wenn die Codierungslängen der Elemente groß sind, z. B. bei großen Integer-Typen oder langen Strings, was das Vergleichen von Elementen teuer macht. Darüber hinaus ist der Vergleich von Gleitkommawerten (die gebräuchlichste digitale Darstellung von reellen Zahlen ) oft teurer als der Vergleich von ganzen Zahlen oder kurzen Strings.

Bei den meisten Computerarchitekturen verfügt der Prozessor über einen vom RAM getrennten Hardware- Cache . Da sie sich im Prozessor selbst befinden, ist der Zugriff auf Caches viel schneller, speichert jedoch normalerweise viel weniger Daten als RAM. Daher speichern die meisten Prozessoren Speicherorte, auf die kürzlich zugegriffen wurde, zusammen mit Speicherorten in der Nähe davon. Wenn beispielsweise auf ein Array-Element zugegriffen wird, kann das Element selbst zusammen mit den Elementen, die nahe bei ihm im RAM gespeichert sind, gespeichert werden, wodurch es schneller wird, sequenziell auf Array-Elemente zuzugreifen, die im Index nahe beieinander liegen ( Lokalität der Referenz ). . Auf einem sortierten Array kann die binäre Suche zu entfernten Speicherorten springen, wenn das Array groß ist, im Gegensatz zu Algorithmen (wie z. B. lineare Suche und lineares Prüfen in Hash-Tabellen ), die nacheinander auf Elemente zugreifen. Dies verlängert die Laufzeit der binären Suche nach großen Arrays auf den meisten Systemen geringfügig.

Binäre Suche im Vergleich zu anderen Schemata

Sortierte Arrays mit binärer Suche sind eine sehr ineffiziente Lösung, wenn Einfüge- und Löschoperationen mit dem Abrufen verschachtelt sind, was für jede dieser Operationen Zeit in Anspruch nimmt . Außerdem können sortierte Arrays die Speichernutzung erschweren, insbesondere wenn Elemente häufig in das Array eingefügt werden. Es gibt andere Datenstrukturen, die ein viel effizienteres Einfügen und Löschen unterstützen. Die binäre Suche kann verwendet werden, um einen genauen Abgleich und eine Satzmitgliedschaft durchzuführen (bestimmen, ob ein Zielwert in einer Sammlung von Werten enthalten ist). Es gibt Datenstrukturen, die einen schnelleren exakten Abgleich und eine schnellere Gruppenmitgliedschaft unterstützen. Im Gegensatz zu vielen anderen Suchschemata kann die binäre Suche jedoch für eine effiziente ungefähre Übereinstimmung verwendet werden, wobei solche Übereinstimmungen normalerweise unabhängig von der Art oder Struktur der Werte selbst rechtzeitig durchgeführt werden. Darüber hinaus gibt es einige Operationen, wie das Finden des kleinsten und größten Elements, die effizient in einem sortierten Array ausgeführt werden können.

Lineare Suche

Die lineare Suche ist ein einfacher Suchalgorithmus, der jeden Datensatz überprüft, bis er den Zielwert findet. Eine lineare Suche kann in einer verknüpften Liste durchgeführt werden, die ein schnelleres Einfügen und Löschen als ein Array ermöglicht. Die binäre Suche ist bei sortierten Arrays schneller als die lineare Suche, außer wenn das Array kurz ist, obwohl das Array vorher sortiert werden muss. Alle Sortieralgorithmen, die auf Vergleichselementen basieren, wie Quicksort und Mergesort , erfordern im schlimmsten Fall zumindest Vergleiche. Im Gegensatz zur linearen Suche kann die binäre Suche für eine effiziente ungefähre Übereinstimmung verwendet werden. Es gibt Operationen wie das Finden des kleinsten und größten Elements, die in einem sortierten Array effizient durchgeführt werden können, aber nicht in einem unsortierten Array.

Bäume

Binäre Suchbäume werden unter Verwendung eines der binären Suche ähnlichen Algorithmus durchsucht.

Ein binärer Suchbaum ist eine binäre Baumdatenstruktur , die nach dem Prinzip der binären Suche arbeitet. Die Datensätze des Baums sind in sortierter Reihenfolge angeordnet, und jeder Datensatz im Baum kann mit einem der binären Suche ähnlichen Algorithmus durchsucht werden, wobei eine durchschnittliche logarithmische Zeit benötigt wird. Einfügen und Löschen erfordern auch in binären Suchbäumen durchschnittlich logarithmische Zeit. Dies kann schneller sein als das lineare Einfügen und Löschen von sortierten Arrays, und binäre Bäume behalten die Fähigkeit, alle möglichen Operationen an einem sortierten Array durchzuführen, einschließlich Bereichs- und Näherungsabfragen.

Die binäre Suche ist jedoch normalerweise effizienter für die Suche, da binäre Suchbäume höchstwahrscheinlich nicht perfekt ausbalanciert sind, was zu einer etwas schlechteren Leistung als die binäre Suche führt. Dies gilt sogar für ausgeglichene binäre Suchbäume , binäre Suchbäume, die ihre eigenen Knoten ausgleichen, da sie selten den Baum mit den wenigsten Ebenen erzeugen. Außer bei ausgeglichenen binären Suchbäumen kann der Baum mit wenigen internen Knoten mit zwei Kindern stark unausgeglichen sein, was dazu führt, dass sich die durchschnittliche und die schlimmste Suchzeit Vergleiche nähern . Binäre Suchbäume benötigen mehr Platz als sortierte Arrays.

Binäre Suchbäume eignen sich für die schnelle Suche im externen Speicher auf Festplatten, da binäre Suchbäume effizient in Dateisystemen strukturiert werden können. Der B-Baum verallgemeinert diese Methode der Baumorganisation. B-Trees werden häufig verwendet, um Langzeitspeicher wie Datenbanken und Dateisysteme zu organisieren .

Hashing

Um assoziative Arrays zu implementieren , sind Hash-Tabellen , eine Datenstruktur, die Schlüssel mithilfe einer Hash-Funktion auf Datensätze abbildet , im Allgemeinen schneller als die binäre Suche in einem sortierten Array von Datensätzen. Die meisten Hash-Tabellen-Implementierungen benötigen im Durchschnitt nur amortisierte konstante Zeit. Hashing ist jedoch nicht für ungefähre Übereinstimmungen nützlich, wie zum Beispiel die Berechnung des nächstkleineren, nächstgrößeren und nächsten Schlüssels, da die einzige Information bei einer fehlgeschlagenen Suche darin besteht, dass das Ziel in keinem Datensatz vorhanden ist. Die binäre Suche ist ideal für solche Übereinstimmungen und führt sie in logarithmischer Zeit durch. Die binäre Suche unterstützt auch ungefähre Übereinstimmungen. Einige Operationen, wie das Finden des kleinsten und größten Elements, können bei sortierten Arrays effizient durchgeführt werden, nicht jedoch bei Hash-Tabellen.

Mitgliedschaftsalgorithmen festlegen

Ein verwandtes Problem bei der Suche ist die Set-Mitgliedschaft . Jeder Algorithmus, der nachschlagen kann, wie die binäre Suche, kann auch für die Gruppenmitgliedschaft verwendet werden. Es gibt andere Algorithmen, die spezieller für die Setzugehörigkeit geeignet sind. Ein Bit-Array ist das einfachste und nützlichste, wenn der Schlüsselbereich begrenzt ist. Es speichert kompakt eine Sammlung von Bits , wobei jedes Bit einen einzelnen Schlüssel innerhalb des Schlüsselbereichs darstellt. Bit-Arrays sind sehr schnell und benötigen nur Zeit. Der Judy1-Typ des Judy-Arrays verarbeitet 64-Bit-Schlüssel effizient.

Für ungefähre Ergebnisse speichern Bloom-Filter , eine weitere probabilistische Datenstruktur basierend auf Hashing, einen Satz von Schlüsseln, indem sie die Schlüssel unter Verwendung eines Bit-Arrays und mehrerer Hash-Funktionen codieren . Bloom-Filter sind in den meisten Fällen viel platzsparender als Bit-Arrays und nicht viel langsamer: Bei Hash-Funktionen benötigen Mitgliedschaftsabfragen nur Zeit. Bloom-Filter leiden jedoch unter falsch positiven Ergebnissen .

Andere Datenstrukturen

Es gibt Datenstrukturen, die die binäre Suche in einigen Fällen sowohl für die Suche als auch für andere Operationen, die für sortierte Arrays verfügbar sind, verbessern können. Zum Beispiel können Suchen, ungefähre Übereinstimmungen und die Operationen, die für sortierte Arrays verfügbar sind, effizienter als binäre Suche an spezialisierten Datenstrukturen wie Van-Emde-Boas-Bäumen , Fusionsbäumen , Versuchen und Bit-Arrays durchgeführt werden . Diese spezialisierten Datenstrukturen sind normalerweise nur schneller, weil sie die Eigenschaften von Schlüsseln mit einem bestimmten Attribut (normalerweise Schlüssel mit kleinen ganzen Zahlen) ausnutzen und daher für Schlüssel ohne dieses Attribut zeit- oder platzaufwendig sind. Solange die Schlüssel geordnet werden können, können diese Operationen unabhängig von den Schlüsseln immer zumindest effizient auf einem sortierten Array durchgeführt werden. Einige Strukturen, z. B. Judy-Arrays, verwenden eine Kombination von Ansätzen, um dies zu mildern, während die Effizienz und die Fähigkeit zur Durchführung eines ungefähren Abgleichs beibehalten werden.

Variationen

Einheitliche binäre Suche

Die einheitliche binäre Suche speichert die Differenz zwischen dem aktuellen und den beiden nächstmöglichen mittleren Elementen anstelle spezifischer Grenzen.

Die einheitliche binäre Suche speichert anstelle der unteren und oberen Grenzen die Differenz im Index des mittleren Elements von der aktuellen Iteration zur nächsten Iteration. Eine Nachschlagetabelle, die die Unterschiede enthält, wird vorher berechnet. Wenn das zu durchsuchende Array beispielsweise [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] ist , wäre das mittlere Element ( ) 6 . In diesem Fall ist das mittlere Element des linken Subarrays ( [1, 2, 3, 4, 5] ) 3 und das mittlere Element des rechten Subarrays ( [7, 8, 9, 10, 11] ) 9 . Eine einheitliche binäre Suche würde den Wert 3 speichern, da sich beide Indizes um denselben Betrag von 6 unterscheiden . Um den Suchraum zu verkleinern, addiert oder subtrahiert der Algorithmus diese Änderung vom Index des mittleren Elements. Die einheitliche binäre Suche kann auf Systemen schneller sein, bei denen es ineffizient ist, den Mittelpunkt zu berechnen, wie z. B. auf Dezimalcomputern .

Exponentielle Suche

Visualisierung der exponentiellen Suche nach der oberen Schranke für die nachfolgende binäre Suche

Die exponentielle Suche erweitert die binäre Suche auf unbegrenzte Listen. Es beginnt damit, das erste Element mit einem Index zu finden, der sowohl eine Zweierpotenz als auch größer als der Zielwert ist. Danach legt es diesen Index als obere Grenze fest und wechselt zur binären Suche. Eine Suche dauert Iterationen, bevor die binäre Suche gestartet wird, und höchstens Iterationen der binären Suche, wobei die Position des Zielwerts ist. Die exponentielle Suche funktioniert bei begrenzten Listen, wird jedoch nur dann zu einer Verbesserung gegenüber der binären Suche, wenn der Zielwert am Anfang des Arrays liegt.

Interpolationssuche

Visualisierung der Interpolationssuche mit linearer Interpolation. In diesem Fall ist keine Suche erforderlich, da die Schätzung der Position des Ziels innerhalb des Arrays korrekt ist. Andere Implementierungen können eine andere Funktion zum Schätzen des Standorts des Ziels spezifizieren.

Anstatt den Mittelpunkt zu berechnen, schätzt die Interpolationssuche die Position des Zielwerts unter Berücksichtigung der niedrigsten und höchsten Elemente im Array sowie der Länge des Arrays. Es funktioniert auf der Grundlage, dass der Mittelpunkt in vielen Fällen nicht die beste Schätzung ist. Wenn sich der Zielwert beispielsweise in der Nähe des höchsten Elements im Array befindet, befindet er sich wahrscheinlich am Ende des Arrays.

Eine übliche Interpolationsfunktion ist die lineare Interpolation . Wenn ist das Array, sind die untere bzw. obere Grenze und ist das Ziel, dann wird geschätzt, dass das Ziel ungefähr auf dem Weg zwischen und liegt . Wenn eine lineare Interpolation verwendet wird und die Verteilung der Array-Elemente gleichförmig oder nahezu gleichförmig ist, führt die Interpolationssuche Vergleiche durch.

In der Praxis ist die Interpolationssuche für kleine Arrays langsamer als die binäre Suche, da die Interpolationssuche zusätzliche Berechnungen erfordert. Seine Zeitkomplexität wächst langsamer als die binäre Suche, aber dies kompensiert nur die zusätzliche Berechnung für große Arrays.

Gebrochene Kaskadierung

Bei der fraktionierten Kaskadierung hat jedes Array Zeiger auf jedes zweite Element eines anderen Arrays, sodass nur eine binäre Suche durchgeführt werden muss, um alle Arrays zu durchsuchen.

Fractional Cascading ist eine Technik, die die binäre Suche nach demselben Element in mehreren sortierten Arrays beschleunigt. Das separate Durchsuchen jedes Arrays erfordert Zeit, wobei die Anzahl der Arrays angegeben ist. Die fraktionierte Kaskadierung reduziert dies, indem in jedem Array spezifische Informationen über jedes Element und seine Position in den anderen Arrays gespeichert werden.

Die fraktionierte Kaskadierung wurde ursprünglich entwickelt, um verschiedene rechnerische Geometrieprobleme effizient zu lösen . Die fraktionierte Kaskadierung wurde an anderer Stelle angewendet, beispielsweise beim Data Mining und beim Internet Protocol- Routing.

Verallgemeinerung auf Grafiken

Die binäre Suche wurde verallgemeinert, um mit bestimmten Diagrammtypen zu arbeiten, bei denen der Zielwert in einem Scheitelpunkt anstelle eines Array-Elements gespeichert wird. Binäre Suchbäume sind eine solche Verallgemeinerung – wenn ein Scheitelpunkt (Knoten) im Baum abgefragt wird, lernt der Algorithmus entweder, dass der Scheitelpunkt das Ziel ist oder in welchem ​​Unterbaum sich das Ziel befinden würde. Dies kann jedoch weiter verallgemeinert werden als folgt: Bei einem ungerichteten, positiv gewichteten Graphen und einem Zielscheitel lernt der Algorithmus beim Abfragen eines Scheitels, dass dieser gleich dem Ziel ist, oder er erhält eine einfallende Kante, die auf dem kürzesten Weg vom abgefragten Scheitel zum Ziel liegt. Der standardmäßige binäre Suchalgorithmus ist einfach der Fall, wenn der Graph ein Pfad ist. Ähnlich sind binäre Suchbäume der Fall, bei denen die Kanten zum linken oder rechten Teilbaum gegeben sind, wenn der abgefragte Scheitelpunkt ungleich dem Ziel ist. Für alle ungerichteten, positiv gewichteten Graphen gibt es einen Algorithmus, der bei Abfragen im schlimmsten Fall den Zielknoten findet.

Verrauschte binäre Suche

Bei der verrauschten binären Suche besteht eine gewisse Wahrscheinlichkeit, dass ein Vergleich falsch ist.

Verrauschte binäre Suchalgorithmen lösen den Fall, in dem der Algorithmus Elemente des Arrays nicht zuverlässig vergleichen kann. Für jedes Elementpaar besteht eine gewisse Wahrscheinlichkeit, dass der Algorithmus den falschen Vergleich anstellt. Eine verrauschte binäre Suche kann die richtige Position des Ziels mit einer gegebenen Wahrscheinlichkeit finden, die die Zuverlässigkeit der erhaltenen Position steuert. Jedes verrauschte binäre Suchverfahren muss im Durchschnitt mindestens Vergleiche durchführen, wo die binäre Entropiefunktion und die Wahrscheinlichkeit, dass das Verfahren die falsche Position liefert, ist. Das Problem der verrauschten binären Suche kann als ein Fall des Rényi-Ulam-Spiels betrachtet werden , einer Variante von Twenty Questions, bei der die Antworten möglicherweise falsch sind.

Quantenbinäre Suche

Klassische Computer sind bei der Durchführung einer binären Suche auf den schlimmsten Fall von exakten Iterationen beschränkt. Quantenalgorithmen für die binäre Suche sind immer noch an einen Teil der Abfragen gebunden (die Iterationen des klassischen Verfahrens darstellen), aber der konstante Faktor ist kleiner als eins, was für eine geringere Zeitkomplexität auf Quantencomputern sorgt . Jedes exakte quantenbinäre Suchverfahren – also ein Verfahren, das immer das richtige Ergebnis liefert – erfordert im schlimmsten Fall, wo der natürliche Logarithmus ist, mindestens Abfragen . Es gibt ein exaktes quantenbinäres Suchverfahren, das im schlimmsten Fall in Abfragen ausgeführt wird. Im Vergleich dazu ist Grovers Algorithmus der optimale Quantenalgorithmus zum Durchsuchen einer ungeordneten Liste von Elementen und erfordert Abfragen.

Geschichte

Die Idee, eine Liste von Elementen zu sortieren, um eine schnellere Suche zu ermöglichen, geht auf die Antike zurück. Das früheste bekannte Beispiel war die Inakibit-Anu-Tafel aus Babylon aus dem Jahr c.  200 v . Die Tafel enthielt etwa 500 sexagesimale Zahlen und deren Kehrwerte in lexikographischer Reihenfolge sortiert , was die Suche nach einem bestimmten Eintrag erleichterte. Außerdem wurden auf den ägäischen Inseln mehrere Namenslisten entdeckt, die nach ihrem Anfangsbuchstaben sortiert waren . Katholikon , ein lateinisches Wörterbuch, das 1286 n. Chr. fertiggestellt wurde, war das erste Werk, das Regeln für die Sortierung von Wörtern in alphabetischer Reihenfolge beschrieb, im Gegensatz zu nur den ersten paar Buchstaben.

Im Jahr 1946 erwähnte John Mauchly die binäre Suche zum ersten Mal als Teil der Moore School Lectures , einem bahnbrechenden und grundlegenden College-Kurs in Informatik. 1957 veröffentlichte William Wesley Peterson die erste Methode zur Interpolationssuche. Jeder veröffentlichte binäre Suchalgorithmus funktionierte nur für Arrays, deren Länge eins kleiner als eine Potenz von zwei ist, bis 1960 Derrick Henry Lehmer einen binären Suchalgorithmus veröffentlichte, der für alle Arrays funktionierte. 1962 stellte Hermann Bottenbruch eine ALGOL 60- Implementierung der binären Suche vor, die den Vergleich auf Gleichheit ans Ende setzte , die durchschnittliche Anzahl der Iterationen um eins erhöhte, aber die Anzahl der Vergleiche pro Iteration auf eins reduzierte. Die einheitliche binäre Suche wurde 1971 von AK Chandra von der Stanford University entwickelt . 1986 führten Bernard Chazelle und Leonidas J. Guibas die fraktionierte Kaskadierung als Methode zur Lösung zahlreicher Suchprobleme in der Computergeometrie ein .

Umsetzungsfragen

Obwohl die Grundidee der binären Suche vergleichsweise einfach ist, können die Details überraschend knifflig sein

–  Donald Knuth

Als Jon Bentley in einem Kurs für professionelle Programmierer die binäre Suche als Problem zuordnete, stellte er fest, dass neunzig Prozent nach mehreren Stunden Arbeit daran keine richtige Lösung lieferten, hauptsächlich weil die falschen Implementierungen nicht ausgeführt wurden oder in seltenen Fällen eine falsche Antwort lieferten Randfälle . Eine 1988 veröffentlichte Studie zeigt, dass nur in fünf von zwanzig Lehrbüchern ein genauer Code dafür gefunden wird. Darüber hinaus enthielt Bentleys eigene Implementierung der binären Suche, die in seinem 1986 erschienenen Buch Programming Pearls veröffentlicht wurde , einen Überlauffehler , der über zwanzig Jahre lang unentdeckt blieb. Die Implementierung der binären Suche in der Java-Programmiersprachenbibliothek hatte mehr als neun Jahre lang denselben Überlauffehler.

In einer praktischen Implementierung haben die zur Darstellung der Indizes verwendeten Variablen oft eine feste Größe (Ganzzahlen), was bei sehr großen Arrays zu einem arithmetischen Überlauf führen kann . Wenn der Mittelpunkt der Spanne als berechnet wird , kann der Wert von den Bereich der Ganzzahlen des zum Speichern des Mittelpunkts verwendeten Datentyps überschreiten, selbst wenn und innerhalb des Bereichs liegen. Wenn und nicht negativ sind, kann dies vermieden werden, indem der Mittelpunkt als berechnet wird .

Eine Endlosschleife kann auftreten, wenn die Austrittsbedingungen für die Schleife nicht richtig definiert sind. Sobald überschritten ist , ist die Suche fehlgeschlagen und muss das Fehlschlagen der Suche mitteilen. Außerdem muss die Schleife verlassen werden, wenn das Zielelement gefunden wird, bzw. bei einer Implementierung, bei der diese Prüfung ans Ende verschoben wird, eine Prüfung, ob die Suche erfolgreich war oder fehlgeschlagen ist, am Ende vorhanden sein. Bentley stellte fest, dass die meisten Programmierer, die die binäre Suche falsch implementierten, einen Fehler bei der Definition der Ausgangsbedingungen machten.

Bibliotheksunterstützung

Die Standardbibliotheken vieler Sprachen enthalten binäre Suchroutinen:

  • C stellt die Funktion bsearch() in seiner Standardbibliothek bereit , die normalerweise über die binäre Suche implementiert wird, obwohl der offizielle Standard dies nicht erfordert.
  • C ++ ‚s Standard Template Library bietet die Funktionen binary_search(), lower_bound(), upper_bound()und equal_range().
  • D ‚s - Standardbibliothek Phobos, in std.rangebietet Modul einen Typen SortedRange(zurückgegeben durch sort()und assumeSorted()Funktionen) mit Methoden contains(), equaleRange(), lowerBound()und trisect(), die für die Bereiche , die durch Standard - Binär - Suchtechniken verwenden , die mit wahlfreiem Zugriff bieten.
  • COBOL stellt das SEARCH ALLVerb zum Ausführen binärer Suchen in COBOL-geordneten Tabellen bereit .
  • Das sortStandardbibliothekspaket von Go enthält die Funktionen Search, SearchInts, SearchFloat64s, und SearchStrings, die die allgemeine binäre Suche implementieren, sowie spezifische Implementierungen zum Durchsuchen von Teilen von ganzen Zahlen, Gleitkommazahlen bzw. Strings.
  • Java bietet in den Klassen und im Standardpaket einen Satz überladener binarySearch() statischer Methoden , um binäre Suchen auf Java-Arrays bzw. auf s durchzuführen .ArraysCollectionsjava.utilList
  • Microsoft ‚s .NET Framework 2.0 bietet statische generische Versionen des binären Suchalgorithmus in seiner Sammlung Basisklassen. Ein Beispiel wäre die System.ArrayMethode von BinarySearch<T>(T[] array, T value).
  • Für Objective-C stellt das Cocoa- Framework die NSArray -indexOfObject:inSortedRange:options:usingComparator:Methode in Mac OS X 10.6+ bereit. Auch das Core Foundation C-Framework von Apple enthält eine CFArrayBSearchValues()Funktion.
  • Python stellt das bisectModul bereit .
  • Die Array-Klasse von Ruby enthält eine bsearchMethode mit integriertem ungefähren Abgleich.

Siehe auch

  • Bisektionsmethode  – Algorithmus zum Finden einer Nullstelle einer Funktion – die gleiche Idee, die verwendet wird, um Gleichungen in den reellen Zahlen zu lösen
  • Multiplikative Binärsuche  – Binäre Suchvariante mit vereinfachter Mittelpunktberechnung

Hinweise und Referenzen

Dieser Artikel wurde 2018 beim WikiJournal of Science zur externen wissenschaftlichen Begutachtung eingereicht ( Gutachterberichte ). Der aktualisierte Inhalt wurde unter einer CC-BY-SA-3.0- Lizenz ( 2019 ) wieder in die Wikipedia-Seite integriert . Die rezensierte Version des Datensatzes ist: Anthony Lin; et al. (2. Juli 2019). "Binärer Suchalgorithmus" (PDF) . WikiJournal of Science . 2 (1): 5. doi : 10.15347/WJS/2019.005 . ISSN  2470-6345 . Wikidata  Q81434400 .

Anmerkungen

Zitate

Quellen

Externe Links