Es gibt zwei Gründe für die binäre Suche mit einem Vergleich pro Iteration. Das Weniger wichtig ist die Leistung. Frühzeitige Erkennung einer exakten Übereinstimmung mit zwei Vergleiche pro Iteration sparen eine durchschnittliche Iteration der Schleife, während (vorausgesetzt, Vergleiche beinhalten signifikante Arbeit) binäre Suche mit einem der Vergleich pro Iteration halbiert die Arbeit pro Iteration fast.
Binäre Suche nach einem Array von ganzen Zahlen, macht wahrscheinlich keinen großen Unterschied
in jedem Fall. Selbst mit einem ziemlich teuren Vergleich, asymptotisch die
Leistung ist die gleiche, und die Hälfte eher als minus eins ist wahrscheinlich nicht wert
in den meisten Fällen verfolgen. Außerdem werden teure Vergleiche oft als Funktionen codiert, die für < , == oder > negativ, null oder positiv sind, so dass Sie beide Vergleiche für ziemlich genau den Preis von eins erhalten können.
Der wichtige Grund, binäre Suchen mit einem Vergleich pro Iteration durchzuführen, ist weil Sie mehr nützliche Ergebnisse als nur einige gleichwertige erhalten können. Die Hauptsache Suchen, die Sie tun können, sind ...
Dies alles reduziert sich auf den gleichen Basisalgorithmus. Das gut genug verstehen dass Sie alle Varianten leicht codieren können, ist nicht so schwierig, aber ich habe es nicht wirklich eine gute Erklärung gesehen - nur Pseudocode und mathematische Beweise. Dies ist mein Versuch einer Erklärung.
Es gibt Spiele, bei denen es darum geht, einem Ziel so nahe wie möglich zu kommen ohne Überschwingen. Ändere das zu "Unterschießen", und das ist was "Finde First & gt; "tut. Betrachten Sie die Bereiche in einem bestimmten Stadium während der Suche ...
%Vor%Der Bereich zwischen der aktuellen oberen und unteren Grenze muss noch durchsucht werden. Unser Ziel ist (normalerweise) dort irgendwo, aber wir wissen noch nicht wo. Das Interessanter Punkt über Gegenstände über der Obergrenze ist, dass sie legal sind das Gefühl, dass sie größer sind als das Ziel. Wir können das nur sagen über der aktuellen Obergrenze liegt unsere bisher beste Lösung. Das können wir sogar sagen gleich zu Beginn, obwohl es wahrscheinlich keinen Gegenstand an dieser Position gibt - in einem Sinn, wenn es keine gültige In-Range-Lösung gibt, die beste Lösung, die nicht widerlegt wurde, ist gleich hinter der Obergrenze.
Bei jeder Iteration wählen wir ein Element aus, das zwischen der oberen und unteren Grenze verglichen wird. Bei der binären Suche ist das ein gerundeter halber Artikel. Für die binäre Baumsuche ist es diktiert von der Struktur des Baumes. Das Prinzip ist in beiden Richtungen gleich.
Wenn wir nach einem Gegenstand suchen, der größer als unser Ziel ist, vergleichen wir den Testgegenstand
mit Item [testpos] > goal . Wenn das Ergebnis falsch ist, haben wir überschritten (oder
unterschwellig) unser Ziel, so behalten wir unsere bestehende Best-so-Far-Lösung bei und passen uns an
unsere untere Grenze nach oben. Wenn das Ergebnis wahr ist, haben wir einen neuen Best-so-far gefunden
Lösung, also passen wir die obere Grenze an, um das zu reflektieren.
Wie auch immer, wir wollen dieses Testobjekt nie wieder vergleichen, also passen wir es an gebunden, um das Testobjekt aus dem zu durchsuchenden Bereich zu entfernen (nur eben). Sein Unachtsamerweise führt dies in der Regel zu unendlichen Schleifen.
Normalerweise werden halboffene Bereiche verwendet - eine inklusive Untergrenze und eine Exklusivgrenze
obere Grenze. Bei Verwendung dieses Systems befindet sich das Element am oberen Begrenzungsindex nicht in der
Suchbereich (zumindest jetzt nicht), aber ist die beste Lösung. Wenn du
verschiebe die untere Grenze nach oben, verschiebe sie nach testpos+1 (um das Element, das du gerade hast, auszuschließen)
aus dem Sortiment getestet). Wenn Sie die obere Grenze nach unten verschieben, verschieben Sie sie nach
testpos (die obere Grenze ist sowieso exklusiv).
Wenn der Bereich zwischen den unteren und oberen Grenzen leer ist (halboffen, Wenn beide den gleichen Index haben), ist Ihr Ergebnis Ihr bisher bestes Ergebnis Lösung, knapp über der Obergrenze (dh am Obergrenze Index für halboffen).
Also ist der volle Algorithmus ...
%Vor% Um von first key > goal zu first key >= goal zu wechseln, wechseln Sie buchstäblich
der Vergleichsoperator in der if -Zeile. Der relative Operator und das Ziel könnten durch einen einzigen Parameter ersetzt werden - eine Prädikatfunktion, die true zurückgibt, wenn (und nur wenn) ihr Parameter auf der Größer-als-Seite des Ziels liegt.
Das gibt Ihnen "zuerst & gt;" und "zuerst & gt;=". Um "first ==" zu erhalten, verwenden Sie "first & gt;=" und Fügen Sie eine Gleichheitsprüfung hinzu, nachdem die Schleife beendet wurde.
Für "last & lt;" usw., das Prinzip ist das gleiche wie oben, aber der Bereich ist reflektiert. Dies bedeutet nur, dass Sie die gebundenen Anpassungen (aber nicht die Kommentar) sowie den Betreiber wechseln. Aber bevor Sie das tun, überlegen Sie Folgendes ...
%Vor%Auch ...
Wenn wir während der Suche unsere Grenzen verschieben, werden beide Seiten auf das Ziel zu bewegt, bis sie sich am Ziel treffen.Und genau unter der Untergrenze befindet sich ein spezielles Element, genau wie es direkt über der Obergrenze liegt ...
%Vor%In gewisser Weise haben wir also zwei komplementäre Suchvorgänge gleichzeitig. Wenn sich die obere und untere Grenze treffen, haben wir ein nützliches Suchergebnis auf jeder Seite dieser einzelnen Grenze.
Für alle Fälle besteht die Möglichkeit, dass ein Original "imaginär" out-of-bounds wird
best-so-far Position war dein Endergebnis (es gab keine Übereinstimmung in der
Suchbereich). Dies muss überprüft werden, bevor ein abschließender == Check für die
erste == und letzte == Fälle. Es könnte auch ein nützliches Verhalten sein - z. ob
Sie suchen nach der Position, an der Sie Ihr Zielelement einfügen möchten
Das Ende Ihrer vorhandenen Artikel ist das Richtige, wenn Sie alle vorhandenen Artikel verwenden
sind kleiner als dein Zielgegenstand.
Ein paar Hinweise zur Auswahl der Testpos ...
%Vor% Zunächst einmal wird das niemals überlaufen, im Gegensatz zu dem offensichtlicheren ((lowerbound +
upperbound)/2) . Es funktioniert auch mit Zeigern sowie Integer
Indizes.
Zweitens wird angenommen, dass die Division abgerundet wird. Abrundung für Nicht-Negative ist OK (alles, was Sie in C sicher sein können), da der Unterschied immer nicht negativ ist trotzdem.
Dies ist ein Aspekt, der beachtet werden muss, wenn Sie nicht halb geöffnet verwenden Bereiche - Stellen Sie jedoch sicher, dass die Testposition innerhalb des Suchbereichs liegt und nicht nur außerhalb (auf einer der bereits gefundenen Best-So-Fern-Positionen).
Schließlich ist in einer binären Baumsuche das Verschieben von Grenzen implizit und die
Die Wahl von testpos ist in die Struktur des Baumes eingebaut (was sein kann
unausgewogen), doch gelten die gleichen Prinzipien für das, was die Suche tut. In diesem
In diesem Fall wählen wir unseren Child-Knoten, um die impliziten Bereiche zu verkleinern. Für das erste Spiel
Fälle, entweder haben wir ein neues kleineres bestes Match gefunden (gehen Sie zu dem niedrigeren Kind in der Hoffnung, ein noch kleineres und besseres zu finden) oder wir haben überstiegen (gehen Sie zum höheren Kind in der Hoffnung, sich zu erholen). Wiederum können die vier Hauptfälle durch Umschalten des Vergleichsoperators behandelt werden.
BTW - es gibt mehr mögliche Operatoren für diesen Template-Parameter. Betrachten Sie ein Array sortiert nach Jahr und Monat. Vielleicht möchten Sie den ersten Artikel für ein bestimmtes Jahr finden. Schreiben Sie dazu eine Vergleichsfunktion, die das Jahr vergleicht und den Monat ignoriert - das Ziel wird als gleich verglichen, wenn das Jahr gleich ist, aber der Zielwert kann ein anderer Typ als der Schlüssel sein, für den nicht einmal ein Monatswert gilt vergleichen. Ich betrachte dies als einen "partiellen Schlüsselvergleich" und stöpse das in Ihre binäre Suchvorlage ein und Sie erhalten, was ich für eine "teilweise Schlüsselsuche" halte.
BEARBEITEN Im folgenden Absatz wurde "31. Dezember 1999 entspricht dem 1. Februar 2000" angegeben. Das würde nicht funktionieren, wenn nicht der gesamte Bereich dazwischen als gleichwertig betrachtet würde. Der Punkt ist, dass sich alle drei Teile des Anfangs- und Enddatums unterscheiden, Sie werden also nicht mit einem "partiellen" Schlüssel beschäftigt, aber die Schlüssel, die für die Suche als gleichwertig betrachtet werden, müssen einen zusammenhängenden Block im Container bilden. was normalerweise einen zusammenhängenden Block in der geordneten Menge möglicher Schlüssel impliziert.
Es ist auch nicht unbedingt nur "Teil" -Tasten. Ihr benutzerdefinierter Vergleich könnte den 31. Dezember 1999 für den 1. Januar 2000 halten, aber alle anderen Daten sind anders. Der Punkt ist der benutzerdefinierte Vergleich muss mit dem ursprünglichen Schlüssel über die Reihenfolge übereinstimmen, aber es ist vielleicht nicht so wählerisch über die Berücksichtigung aller unterschiedlichen Werte - es kann eine Reihe von Schlüsseln als eine "Äquivalenzklasse" behandeln.
Eine zusätzliche Notiz über die Grenzen, die ich eigentlich hätte einfügen sollen, aber ich habe zu dieser Zeit vielleicht noch nicht darüber nachgedacht.
Eine Möglichkeit, über Grenzen nachzudenken, ist, dass sie überhaupt keine item Indizes sind. Eine Grenze ist die Grenzlinie zwischen zwei Elementen, so dass Sie die Begrenzungslinien so einfach nummerieren können, wie Sie die Elemente nummerieren können ...
%Vor%Offensichtlich hängt die Nummerierung der Grenzen mit der Nummerierung der Elemente zusammen. Solange Sie Ihre Schranken von links nach rechts nummerieren und auf die gleiche Weise Ihre Gegenstände nummerieren (in diesem Fall von Null ausgehend), entspricht das Ergebnis effektiv der üblichen halboffenen Konvention.
Es wäre möglich, eine mittlere Grenze zu wählen, um den Bereich genau in zwei zu teilen, aber das ist nicht das, was eine binäre Suche tut. Bei der binären Suche wählen Sie ein zu testendes Element aus - keine Grenze. Dieses Element wird in dieser Iteration getestet und darf nie erneut getestet werden. Daher wird es aus beiden Unterbereichen ausgeschlossen.
%Vor% Also sind die testpos und testpos+1 im Algorithmus die beiden Fälle, in denen der Artikelindex in den gebundenen Index übersetzt wird. Natürlich, wenn die beiden Grenzen gleich sind, gibt es keine Elemente in diesem Bereich zu wählen, so dass die Schleife nicht fortgesetzt werden kann, und das einzige mögliche Ergebnis ist, dass ein gebundener Wert.
Die oben gezeigten Bereiche sind nur die Bereiche, die noch gesucht werden müssen - die Lücke, die wir zwischen den nachgewiesenen niedrigeren und den nachgewiesenen höheren Bereichen schließen wollen.
In diesem Modell sucht die binäre Suche nach der Grenze zwischen zwei geordneten Arten von Werten - jenen, die als "niedriger" klassifiziert sind, und jenen, die als "höher" klassifiziert sind.Der Prädikat-Test klassifiziert ein Element. Es gibt keine "gleiche" Klasse - Schlüsselwerte sind Teil der höheren Klasse (für x[i] >= key ) oder der unteren Klasse (für x[i] > key ).
Tags und Links algorithm binary-search