Ich bin mir nicht sicher, warum List als allgemeine Datenstruktur einen binären Suchalgorithmus haben sollte, wenn die Liste sortiert ist. Wird die get -Methode, die den Index akzeptiert, nicht sequenziell durchlaufen, zumindest nicht für List 's Subtyp LinkedList ? Wenn ja, sehe ich keinen Vorteil der Verwendung von binarySearch im Vergleich mit sequenziellem Vergleich für LinkedList . Natürlich können wir binarySearch mit mehr Sicherheit durchführen, wenn wir List nicht auf ArrayList beschränken.
Stimmt mein Verständnis? Danke.
Es gibt viele Möglichkeiten, List zu implementieren. Es gibt ArrayList , LinkedList , CopyOnWriteArrayList usw. in den Standard-Java-Bibliotheken und eine Menge anderer Implementierungen, die über diese hinausgehen ( VLists , Ringpuffer, schräge Binomiallisten, erweiterbare Arrays , 2-3 Finger Bäume , etc.). Die Idee hinter der Bereitstellung der binären Suche besteht darin, dass zwar nicht alle List-Implementierungen einen wahlfreien Zugriff unterstützen, aber diejenigen, die dies tun, von einer generischen Implementierung der binären Suche profitieren würden, so dass die Autoren jeder Datenstruktur sie nicht von Grund auf neu implementieren müssen. Wenn ich zum Beispiel eine verrückte neue Listenstruktur implementiere, die zufälligen Zugriff unterstützt, kann ich, wenn ich die List-Schnittstelle implementiere, automatisch eine binäre Suche von der Collections-Klasse erhalten.
Interessanterweise wird die binarySearch -Methode so geschrieben, dass sie den Typ von List betrachtet und sieht, ob sie die RandomAccess -Schnittstelle implementiert, bevor sie tatsächlich die binäre Suche ausführt. Wenn die Liste RandomAccess nicht implementiert, verwendet die Methode anstelle einer Standard-Binärsuche eine modifizierte Binärsuche mit Iteratoren, die garantiert höchstens O (n) Iterationen und O (log n) -Vergleiche liefert. Die Idee besteht darin, zu verfolgen, wo die letzte Sonde gelandet ist, dann vorwärts oder rückwärts zu laufen, um die nächste Sondenposition zu finden usw. Die gesamte geleistete Arbeit ist dann höchstens n / 2 + n / 4 + n / 8 + n / 16 + ... = 2n, also im schlimmsten Fall ist es nur doppelt so schlimm wie eine Worst-Case-lineare Suche.
Kurz gesagt, die Bereitstellung einer generischen Implementierung von binarySearch macht es nicht immer möglich, eine Liste schnell nach etwas zu durchsuchen, aber für die Strukturen, die schnellen Zugriff unterstützen, kann es einen großen Unterschied machen und viel Implementierer sparen Zeit. Darüber hinaus bedeutet die grazile Verschlechterung der modifizierten binären Suche, die in O (n) -Zeit ausgeführt wird, dass die Implementierung niemals zu viel schlechter als ein linearer Standard-Scan wird.
Diese Argumentation ähnelt der Argumentation hinter dem Design der C ++ - Algorithmen, die auf generischen Wertebereichen basieren. Die Effizienz dieser Algorithmen könnte viel schlechter sein als eine spezialisierte Version des Algorithmus auf einer Datenbasis-Basis, aber wenn die allgemeine Version verfügbar ist, bedeutet dies, dass alle neuen Container, die Iteratoren unterstützen, automatisch viel mehr Funktionalität zur Verfügung haben in der Schnittstelle angegeben.
Hoffe, das hilft!
Ja, Sie haben recht, wenn eine Liste keinen wahlfreien Zugriff bietet, was bei LinkedList der Fall ist, gibt es keinen Vorteil. Aus dem Javadoc von Collections.binarySearch() :
Diese Methode wird in log (n) Zeit für eine "Direktzugriffs" -Liste ausgeführt (die einen positionsnahen Zugriff mit nahezu konstanter Zeit bereitstellt). Wenn die angegebene Liste die Schnittstelle {@link RandomAccess} nicht implementiert und groß ist, führt diese Methode eine iteratorbasierte binäre Suche durch, die O (n) Link-Traversale und O (Protokoll n) Elementvergleiche durchführt.
Also ist die Komplexität in diesem Fall die gleiche wie im Fall des sequentiellen Vergleichs - O (n). Praktisch glaube ich, dass der sequentielle Vergleich in vielen Fällen schneller sein kann.
Tags und Links algorithm java list data-structures binary-search