In der Informatik, einer binären Suche oder dem Halbzwischenraum-Suchalgorithmus findet die Position eines angegebenen Werts (der Eingang "Schlüssel") innerhalb einer sortierten Reihe. In jedem Schritt vergleicht der Algorithmus den Eingangsschlüsselwert mit dem Schlüsselwert des mittleren Elements der Reihe. Wenn die Schlüssel zusammenpassen, dann ist ein zusammenpassendes Element gefunden worden, so wird sein Index oder Position, zurückgegeben. Sonst, wenn der gesuchte Schlüssel weniger ist als der Schlüssel des mittleren Elements, dann wiederholt der Algorithmus seine Handlung auf der Subreihe links vom mittleren Element oder, wenn der Eingangsschlüssel auf der Subreihe nach rechts größer ist. Wenn die restliche zu suchende Reihe auf die Null reduziert wird, dann kann der Schlüssel nicht in der Reihe und einem speziellen "Nicht gefunden werden gefundene" Anzeige wird zurückgegeben.

Eine binäre Suche Hälften der Zahl von Sachen, um mit jeder Wiederholung zu checken, so einen Artikel ausfindig machend (oder seine Abwesenheit bestimmend), nimmt Zeit in Anspruch. Eine binäre Suche ist ein dichotomic teilen und überwinden Suchalgorithmus.

Übersicht

Die Suche einer sortierten Sammlung ist eine allgemeine Aufgabe. Ein Wörterbuch ist eine sortierte Liste von Wortdefinitionen. In Anbetracht eines Wortes kann man seine Definition finden. Ein Telefonbuch ist eine sortierte Liste der Namen von Leuten, Adressen und Telefonnummern. Das Wissen von jemandes Namen erlaubt demjenigen, ihre Telefonnummer und Adresse schnell zu finden.

Wenn die zu suchende Liste mehr enthält als einige Sachen (ein Dutzend, sagen Sie) eine binäre Suche wird weit weniger Vergleiche verlangen als eine geradlinige Suche, aber es erlegt die Voraussetzung auf, dass die Liste sortiert wird. Ähnlich kann eine Kuddelmuddel-Suche schneller sein als eine binäre Suche, aber erlegt noch größere Voraussetzungen auf. Wenn der Inhalt der Reihe zwischen Suchen modifiziert wird, kann das Aufrechterhalten dieser Voraussetzungen mehr Zeit nehmen als die Suchen! Und wenn es bekannt ist, dass einige Sachen nach viel öfter gesucht werden als andere, und es eingeordnet werden kann, dass diese Sachen am Anfang der Liste sind, dann kann eine geradlinige Suche am besten sein.

Beispiele

Zahl-Ratespiel

Dieses ziemlich einfache Spiel beginnt etwas wie "ich denke an eine ganze Zahl zwischen vierzig und sechzig einschließliche, und zu Ihren Annahmen werde ich 'Hoch', 'Niedrig', oder 'Ja antworten!' wie der Fall sein könnte."

Angenommen, dass N die Zahl von möglichen Werten ist (hier, einundzwanzig, weil "einschließlich" festgesetzt wurde), dann an den meisten Fragen sind erforderlich, die Zahl, seit jeder Frage Hälften des Suchraums zu bestimmen. Bemerken Sie, dass ein weniger Frage (Wiederholung) erforderlich ist als für den allgemeinen Algorithmus, da die Zahl bereits beschränkt wird, innerhalb einer besonderen Reihe zu sein.

Selbst wenn die Zahl, um zu schätzen, willkürlich groß sein kann, in welchem Fall dort nicht ober ist, hat N gebunden, Die Zahl kann in an den meisten Schritten gefunden werden (wo k die (unbekannte) ausgewählte Zahl ist) durch die erste Entdeckung eines durch die wiederholte Verdoppelung gebundenen oberen. Zum Beispiel, wenn die Zahl 11 war, konnte die folgende Folge von Annahmen verwendet werden, um es zu finden: 1, 2, 4, 8, 16, 12, 10, 11

Man konnte auch die Methode erweitern, negative Zahlen einzuschließen; zum Beispiel konnten die folgenden Annahmen verwendet werden, um 13 zu finden: 0, 1, 2, 4, 8, 16, 12, 14, 13.

Wortlisten

Leute verwenden normalerweise eine Mischung der binären Suche und Interpolative-Suchalgorithmen, wenn sie ein Telefonbuch suchen, nach der anfänglichen Annahme nutzen wir die Tatsache aus, dass die Einträge sortiert werden und den erforderlichen Zugang schnell finden können. Zum Beispiel, wenn man nach Smith sucht, wenn Rogers und Thomas gefunden worden sind, kann man zu einer Seite über halbwegs zwischen den vorherigen Annahmen schnipsen. Wenn das Samson zeigt, kann es beschlossen werden, dass Smith irgendwo zwischen den Seiten von Samson und Thomas ist, so können diese geteilt werden.

Anwendungen auf die Kompliziertheitstheorie

Selbst wenn wir keine feste Reihe die Fälle Nummer k darin wissen, können wir noch seinen Wert bestimmen, indem wir einfach ja/no fragen, Fragen der Form "Sind größer k als x?" für eine Nummer x. Weil eine einfache Folge davon, wenn Sie auf die Frage antworten können, "Dieses Eigentum der ganzen Zahl k größer ist als ein gegebener Wert?" in einer Zeitdauer dann können Sie den Wert dieses Eigentums in derselben Zeitdauer mit einem zusätzlichen Faktor dessen finden. Das wird die Verminderung genannt, und es ist wegen dieser Art der Verminderung, die die meisten Kompliziertheitstheoretiker auf Entscheidungsprobleme, Algorithmen konzentrieren, die einen einfachen ja/no Antwort erzeugen.

Nehmen Sie zum Beispiel an, dass wir antworten konnten, "Tut diesen n x n Matrix haben Determinante, die größer ist als k?" in O (n) Zeit. Dann, indem wir binäre Suche verwendet haben, konnten wir (Decke) Determinante selbst in O (nlog d) Zeit finden, wo d die Determinante ist; bemerken Sie, dass d nicht die Größe des Eingangs, aber die Größe der Produktion ist.

Algorithmus

Rekursiv

Eine aufrichtige Durchführung der binären Suche ist rekursiv. Der anfängliche Anruf verwendet die Indizes der kompletten zu suchenden Reihe. Das Verfahren berechnet dann einen Index auf halbem Wege zwischen den zwei Indizes, bestimmt, welche von der zwei Subreihe, um zu suchen, und dann einen rekursiven Anruf tut, diese Subreihe zu suchen. Jeder der Anrufe ist rekursiver Schwanz, so braucht ein Bearbeiter sich keinen neuen Stapel für jeden Anruf entwickeln lassen. Die Variablen und sind die niedrigsten und höchsten einschließlichen Indizes, die gesucht werden.

interne Nummer binary_search (interne Nummer [], int Schlüssel, interne Nummer imin, interne Nummer imax)

{\

//prüfen Sie, wenn Reihe leerer ist

wenn (imax

//Schlüssel ist in der niedrigeren Teilmenge

geben Sie binary_search (A, Schlüssel, imin, imid-1) zurück;

sonst, wenn ([imid]

Es wird mit der Initiale und den Werten und für eine Null gestützte Reihe angerufen.

Wiederholend

Der binäre Suchalgorithmus kann auch wiederholend mit zwei Index-Grenzen ausgedrückt werden, die progressiv die Suchreihe einengen.

interne Nummer binary_search (interne Nummer [], int Schlüssel, interne Nummer imin, interne Nummer imax){\

//setzen Sie fort zu suchen, während [imin, imax] nicht leerer ist

während (imax> = imin)

{\

/* berechnen Sie den Mittelpunkt für grob die gleiche Teilung * /

interne Nummer imid = (imin + imax) / 2;

//bestimmen Sie der Subreihe, zu suchen

wenn ([imid]

//ändern Sie max Index, um niedrigere Subreihe zu suchen

imax = imid - 1;

sonst

//Schlüssel, der am Index imid gefunden ist

geben Sie imid zurück;

}\

//Schlüssel nicht gefundener

geben Sie KEY_NOT_FOUND zurück;

}\</Quelle>

Aufgeschobene Entdeckung der Gleichheit

Die obengenannten wiederholenden und rekursiven Versionen nehmen drei auf dem Schlüsselvergleich gestützte Pfade: ein Pfad für weniger als, ein Pfad für den größeren als und ein Pfad für die Gleichheit. (Es gibt zwei bedingte Zweige.) Wird der Pfad für die Gleichheit nur genommen, wenn die Aufzeichnung schließlich verglichen wird, so wird es selten genommen. Dieser Zweigpfad kann außerhalb der Suchschleife im aufgeschobenen Test auf die Gleichheitsversion des Algorithmus bewegt werden. Der folgende Algorithmus verwendet nur einen bedingten Zweig pro Wiederholung.

interne Nummer binary_search (interne Nummer [], int Schlüssel, interne Nummer imin, interne Nummer imax){\

während (imax> imin)

{\

interne Nummer imid = (imin + imax) / 2;

wenn ([imid]

Die aufgeschobene Entdeckungsannäherung geht der Möglichkeit der frühen Beendigung auf der Entdeckung eines Matchs voran, so wird die Suche über den Klotz (N) Wiederholungen nehmen. Durchschnittlich wird eine erfolgreiche frühe Beendigungssuche viele Wiederholungen nicht sparen.

Der aufgeschobene Entdeckungsalgorithmus hat den Vorteil, dass, wenn die Schlüssel nicht einzigartig sind, es den kleinsten Index (der Startindex) vom Gebiet zurückgibt, wo Elemente den Suchschlüssel haben. Die frühe Beendigungsversion würde das erste Match zurückgeben, das es gefunden hat, und dieses Match überall im Gebiet von gleichen Schlüsseln sein könnte.

Leistung

Mit jedem Test, der scheitert, ein Match an der untersuchten Position zu finden, wird die Suche mit einer oder anderen der zwei Subzwischenräume, jedes am grössten Teil der Hälfte der Größe fortgesetzt. Genauer, wenn die Zahl von Sachen, N, dann seltsam ist, werden beide Subzwischenräume (N - 1)/2 Elemente enthalten, während, wenn N sogar dann die zwei Subzwischenräume ist, N/2 - 1 und N/2 Elemente enthalten.

Wenn die ursprüngliche Zahl von Sachen N dann nach der ersten Wiederholung ist, dort wird an den meisten N/2 restlichen Sachen, dann an den meisten N/4 Sachen an den meisten N/8 Sachen und so weiter sein. Im Grenzfall, wenn der Wert nicht in der Liste ist, muss der Algorithmus fortsetzen zu wiederholen, bis die Spanne leer gemacht worden ist; das wird am grössten Teil von log (N) + 1  Wiederholungen genommen haben, wo der   Notation die Fußboden-Funktion anzeigt, die sein Argument für eine ganze Zahl nach unten abrundet. Diese Grenzfall-Analyse ist dicht: Für jeden N dort besteht eine Abfrage, die genau log (N) + 1  Wiederholungen nimmt. Wenn im Vergleich zur geradlinigen Suche, deren Grenzfall-Verhalten N Wiederholungen ist, wir sehen, dass binäre Suche wesentlich schneller ist, weil N groß wächst. Zum Beispiel, eine Liste von einer Million Sachen zu suchen, nimmt nicht weniger als eine Million Wiederholungen mit der geradlinigen Suche, aber nie wieder als zwanzig Wiederholungen mit der binären Suche. Jedoch kann eine binäre Suche nur durchgeführt werden, wenn die Liste in der sortierten Ordnung ist.

Durchschnittliche Leistung

ist die erwartete Zahl von Untersuchungen in einer durchschnittlichen erfolgreichen Suche, und der Grenzfall, ist gerade eine mehr Untersuchung. Wenn die Liste leer ist, werden keine Untersuchungen überhaupt gemacht.

So ist binäre Suche ein logarithmischer Algorithmus und führt in O Zeit durch. In den meisten Fällen ist es beträchtlich schneller als eine geradlinige Suche. Es kann mit der Wiederholung oder recursion durchgeführt werden. Auf einigen Sprachen wird es rekursiv eleganter ausgedrückt; jedoch in einem C-basierten Sprachschwanz wird recursion nicht beseitigt, und die rekursive Version verlangt mehr Stapel-Raum.

Binäre Suche kann schlecht mit der Speicherhierarchie aufeinander wirken (d. h. versteckend) wegen seiner Natur des zufälligen Zugangs. Für die Suche im Gedächtnis, wenn die zu suchende Spanne klein ist, kann eine geradlinige Suche höhere Leistung einfach haben, weil es bessere Gegend der Verweisung ausstellt. Für die Außensuche muss Sorge genommen werden, oder jede der ersten mehreren Untersuchungen wird zu einer Platte führen suchen. Eine übliche Methodik ist, das binäre Suchen nach geradliniger Suche aufzugeben, sobald die Größe der restlichen Spanne unter einem kleinen Wert solcher als 8 oder 16 oder noch mehr in neuen Computern fällt. Der genaue Wert hängt völlig von der Maschine ab, die den Algorithmus führt.

Bemerken Sie, dass für vielfache Suchen mit einem festen Wert für N, dann (mit der passenden Rücksicht für die Abteilung der ganzen Zahl), die erste Wiederholung immer das mittlere Element an N/2 auswählt, und das zweite immer entweder N/4 oder 3N/4 und so weiter auswählt. So, wenn die Schlüsselwerte der Reihe in einer Art langsamer Lagerung (auf einer Scheibe-Datei im virtuellen Gedächtnis sind, nicht im Gedächtnis auf dem Span der ZE), wird das Behalten jener drei Schlüssel in einer lokalen Reihe für eine spezielle einleitende Suche vermeiden, auf weit getrenntes Gedächtnis zuzugreifen. Das Entwickeln zu sieben oder fünfzehn solchen Werten wird weitere Niveaus an nicht viel Kosten in der Lagerung erlauben. Andererseits, wenn die Suchen häufig und durch viel andere Tätigkeit nicht getrennt sind, werden die verschiedenen Lagerungskontrolleigenschaften des Computers mehr oder weniger oft zugegriffene Elemente in die schnellere Lagerung automatisch fördern.

Wenn vielfache binäre Suchen für denselben Schlüssel in zusammenhängenden Listen durchgeführt werden sollen, kann Bruchkaskadierung verwendet werden, um aufeinander folgende Suchen nach der ersten zu beschleunigen.

Wenn auch in der Theorie binäre Suche fast immer schneller ist, als geradlinige Suche, in der Praxis sogar auf dem Medium Reihe nach Größen geordnet hat (ungefähr 100 Sachen oder weniger) es unausführbar sein könnte, jemals binäre Suche zu verwenden. Auf der größeren Reihe hat es nur Sinn zur binären Suche, wenn die Zahl von Suchen groß genug ist, weil die anfängliche Zeit, um die Reihe zu sortieren, mit vielen geradlinigen Suchen vergleichbar

ist

Schwankungen

Es gibt viele, und sie sind leicht verwirrt. Außerdem ist das Verwenden einer binären Suche innerhalb einer Sortieren-Methode diskutabel.

Exklusive oder einschließliche Grenzen

Die bedeutendsten Unterschiede sind zwischen den "exklusiven" und "einschließlichen" Formen der Grenzen. In der "exklusiven" bestimmten Form ist die zu suchende Spanne (L + 1) zu (R  1), und das kann plump scheinen, als die zu suchende Spanne in der "einschließlichen" Form, als L zu R beschrieben werden konnte. Obwohl sich die Details unterscheiden, sind die zwei Formen gleichwertig, wie durch das Umwandeln einer Version in den anderen gesehen werden kann. Die einschließliche bestimmte Form kann durch das Ersetzen des ganzen Anscheins von "L" durch" (L  1)" und "R" durch" (R + 1)" dann Umordnen erreicht werden. So, der initialisation von L: = 0 wird (L  1): =0 oder L: = 1, und R: = N + 1 wird (R + 1): =N + 1 oder R: = N. So weit, so gut, aber Zeichen, jetzt wo die Änderungen zu L und R nicht mehr einfach den Wert von p zu L oder R als passend übertragen, aber jetzt (R + 1) sein müssen: =p oder R: = p  1, und (L  1): =p oder L: = p + 1.

So wird der Gewinn eines einfacheren initialisation, getan einmal, durch eine kompliziertere Berechnung verloren, und der für jede Wiederholung getan wird. Wenn das nicht genug ist, ist der Test auf eine leere Spanne auch verglichen mit der Einfachheit der Überprüfung komplizierter, dass der Wert von p Null ist. Dennoch wird die einschließliche bestimmte Form in vielen Veröffentlichungen wie Donald Knuth gefunden. Die Kunst der Computerprogrammierung, Bands 3: Sortierend und Suche, die Dritte Ausgabe.

Eine andere allgemeine Schwankung verwendet einschließliche Grenzen für die linken gebundenen aber exklusiven Grenzen für das gebundene Recht. Das wird aus der Tatsache abgeleitet, dass die Grenzen auf einer Sprache mit der Reihe bei Nullpunkteinstellung einfach zu 0 und die Größe der Reihe beziehungsweise initialisiert werden können. Das spiegelt die Weise wider, wie Reihe-Scheiben auf einigen Programmiersprachen vertreten werden.

Mittelpunkt und Breite

Eine völlig verschiedene Schwankung ist mit dem Aufgeben des L und der R Zeigestöcke zu Gunsten von einer aktuellen Position p und einer Breite w verbunden, wo bei jeder Wiederholung p durch + oder  w angepasst wird und w halbiert wird. Professor Knuth bemerkt, dass "Es möglich ist, das zu tun, aber nur wenn äußerste Sorge den Details" - Abschnitt 6.2.1, Seite 414 Der Kunst der Computerprogrammierung, Bands 3 bezahlt wird: Das Sortieren und die Suche, die Dritte Ausgabe, entwerfen einen Algorithmus, mit der weiteren Bemerkung "Sind einfachere Annäherungen zum Misserfolg verloren!"

Suchen Sie Gebiet

Es gibt keine besondere Voraussetzung, dass die Reihe, die wird sucht, die Grenzen 1 zu N hat. Es ist möglich, eine angegebene Reihe, Elemente zuerst zu suchen, um statt 1 zu N zu dauern. Alles, was notwendig ist, ist, dass der initialisation der Grenzen L ist: = der erste  1 und R: = dauern + 1, dann der ganze Erlös wie zuvor.

Die Elemente der Liste sind nicht notwendigerweise alle einzigartig. Wenn man nach einem Wert sucht, der mehrmals in der Liste vorkommt, ist der Index zurückgekehrt wird des zuerst gestoßenen gleichen Elements sein, und das wird nicht dieses des ersten, letzten oder mittleren Elements des Laufs von Elementen des gleichen Schlüssels notwendigerweise sein, aber wird von den Positionen der Werte abhängen. Das Ändern der Liste sogar auf Weisen anscheinend ohne Beziehung wie das Hinzufügen von Elementen anderswohin in der Liste kann das Ergebnis ändern.

Wenn die Position des ersten und/oder letzten gleichen Elements bestimmt werden muss, kann das effizient mit einer Variante der binären Suchalgorithmen getan werden, die nur einen Ungleichheitstest pro Wiederholung durchführen.

Laute Suche

Mehrere Algorithmen, die nah mit oder das Verlängern binärer Suche verbunden sind, bestehen. Zum Beispiel löst laute binäre Suche dieselbe Klasse von Projekten wie regelmäßige binäre Suche mit der zusätzlichen Kompliziertheit, dass jeder gegebene Test einen falschen Wert aufs Geratewohl zurückgeben kann. (Gewöhnlich, die Zahl solcher falschen Ergebnisse werden irgendwie, entweder in der Form einer durchschnittlichen Fehlerrate, oder in der Gesamtzahl von Fehlern begrenzt, die pro Element im Suchraum erlaubt sind.) Sind optimale Algorithmen für mehrere Klassen von lauten binären Suchproblemen bekannt gewesen seit dem Ende von siebziger Jahren, und mehr kürzlich sind optimale Algorithmen für die laute binäre Suche in Quant-Computern (wo mehrere Elemente zur gleichen Zeit geprüft werden können) entdeckt worden.

Durchführungsprobleme

Obwohl die Grundidee der binären Suche verhältnismäßig aufrichtig ist, können die Details überraschend heikler … — Professor Donald Knuth sein

Als Jon Bentley es als ein Problem in einem Kurs für Berufsprogrammierer zugeteilt hat, hat er gefunden, dass erstaunliche neunzig Prozent gescheitert haben, eine binäre Suche richtig nach mehreren Stunden des Arbeitens darauf zu codieren, und eine andere Studie zeigt, dass der genaue Code dafür nur in fünf aus zwanzig Lehrbüchern gefunden wird. Außerdem enthält die eigene Durchführung von Bentley der binären Suche, die in seinem 1986 Buch veröffentlicht ist, Perlen Programmierend, einen Fehler, der unentdeckt seit mehr als zwanzig Jahren geblieben ist.

Arithmetik

In einer praktischen Durchführung werden die Variablen, die verwendet sind, um die Indizes zu vertreten, der begrenzten Größe sein, die nur folglich dazu fähig ist, einen begrenzten Wertbereich zu vertreten. Zum Beispiel können nicht unterzeichnete ganze 32-Bit-Zahlen nur Werte von 0 bis 4294967295 halten. Die meisten binären Suchalgorithmen verwenden unterzeichnete ganze Zahlen von 32 Bit, die nur Werte von-2147483648 bis 2147483647 halten können. Wenn der binäre Suchalgorithmus auf der großen Reihe funktionieren soll, hat das zwei Implikationen:

• Die Werte und müssen beide innerhalb der begrenzten Grenzen des gewählten Typs der ganzen Zahl wiederpräsentabel sein. Deshalb, das nicht unterzeichnete 32-Bit-Beispiel fortsetzend, ist der größte Wert, der nehmen kann, +4294967294, nicht +4294967295. Ein Problem besteht sogar für die "einschließliche" Form der Methode, als ob dann auf der Endwiederholung der Algorithmus versuchen wird, 4294967296 zu versorgen in und zu scheitern. Gleichwertige Probleme gelten für die niedrigere Grenze, wo negativ als werden konnte, wenn das erste Element der Reihe an der Index-Null ist.
• Wenn der Mittelpunkt der Spanne als berechnet wird, dann wird der Wert die Zahl-Reihe überschreiten, wenn größer ist als (für den nicht unterzeichneten) 4294967295/2 oder (für den unterzeichneten) 2147483647/2 und die Suche zum oberen Ende des Suchraums wandert. Das kann durch das Durchführen der Berechnung als vermieden werden. Wenn das Problem für unterzeichnete ganze Zahlen entsteht, ist eine effizientere Alternative durch das Durchführen der Berechnung als, wo den richtigen logischen Verschiebungsmaschinenbediener anzeigt. Zum Beispiel hat dieser Programmfehler in Java SDK an von 1.2 bis 5.0 bestanden und hat in 6.0 befestigt.

Sprachunterstützung

Viele Standardbibliotheken stellen eine Weise zur Verfügung, eine binäre Suche zu tun:

• C stellt Algorithmus-Funktion in seiner Standardbibliothek zur Verfügung.
• C ++ 's stellt STL Algorithmus-Funktionen zur Verfügung, und.
• Java bietet eine Reihe überlasteter statischer Methoden in den Klassen und im Standardpaket an, um binäre Suchen auf der javanischen Reihe und auf s beziehungsweise durchzuführen. Sie müssen Reihe von Primitiven sein, oder die Reihe oder Listen müssen eines Typs sein, der die Schnittstelle durchführt, oder Sie einen kundenspezifischen Gegenstand angeben müssen.
• Das.NET Fachwerk des Microsofts 2.0 Angebote statische allgemeine Versionen des binären Suchalgorithmus in seiner Sammlung stützt Klassen. Ein Beispiel würde 's Methode sein

• Pythonschlange stellt das Modul zur Verfügung.
• COBOL kann binäre Suche auf inneren Tischen mit der Behauptung durchführen.
• Perl kann eine allgemeine binäre Suche mit der CPAN Modul-Suche durchführen:: Binär.
• Das Standardbibliothekspaket von Go enthält Funktionen, und, die allgemeine binäre Suche, sowie spezifische Durchführungen durchführen, um Scheiben von ganzen Zahlen, Schwimmpunkt-Zahlen und Schnuren, respectively.http://golang.org/pkg/sort/ zu suchen
• Für das Ziel-C stellt das Kakao-Fachwerk den NSArray -indexOfObject:inSortedRange:options:usingComparator zur Verfügung: Methode in Mac OS X 10.6 +. Das Kernfundament des Apfels C Fachwerk enthält auch CFArrayBSearchValues Funktion.

Siehe auch

• Interpolationssuche, ähnliche Methode mit der besseren durchschnittlichen Kompliziertheit
• Index (Informationstechnologie), sehr schneller 'lookup' das Verwenden eines Index zum direkt ausgesuchten ein Zugang
• Zweigtisch, Alternative hat 'lookup' Methode für die Entscheidung mit einem Inhaltsverzeichnis versehen, die macht
• Das Selbstausgleichen binären Suchbaums
• Laufzeitanalyse, binäre Suchmethode auf Maschinen von sich unterscheidenden Geschwindigkeiten illustrierend
• Bisektionsverfahren, dieselbe Idee hat gepflegt, Gleichungen in den reellen Zahlen zu lösen
• Donald Knuth. Die Kunst der Computerprogrammierung, Bands 3: Sortierend und Suche, die Dritte Ausgabe. Addison-Wesley, 1997. Internationale Standardbuchnummer 0-201-89685-0. Abschnitt 6.2.1: Einen Bestellten Tisch, Seiten 409-426 suchend.
• Kruse, Robert L.: "Datenstrukturen und Programm-Design in C ++", Prentice-Saal, 1999, internationale Standardbuchnummer 0-13-768995-0, Seite 280.
• Netty van Gasteren, Wim Feijen. Die Binäre Suche Wieder besucht, AvG127/WF214, 1995. (untersucht die Fundamente der binären Suche, das Mythos entlarvend, das sie nur auf die sortierte Reihe anwendet)

Links

• NIST Wörterbuch von Algorithmen und Datenstrukturen: binäre Suche
• Google Forschung: Fast Ganzer Binary Searches und Mergesorts werden Gebrochen
• Binäre Suche, die auf 12 Sprachen durchgeführt ist