Warum verwendet der Mittelwertalgorithmus für die binäre Suche
? %Vor%statt
%Vor%Ihre Frage ist für Python getaggt, also werde ich für Python antworten. Kurz gesagt, es nicht:
Die Python-Implementierung oben in den Dokumenten verwendet die letztere Konstruktion. Wie die Leute in den Kommentaren darauf hingewiesen haben, müssen einige Sprachen respektiert werden. Überlauf . Python ist keiner davon und hat beliebig viele Ganzzahlen.
In den Kommentaren wurde spekuliert, dass jemand, der aus einer C-ähnlichen Sprache portiert, die akzeptablere Konstruktion für diese Sprache kopiert. Das ist möglich. Jemand anders bemerkte, dass einer schneller sein könnte als der andere; Eine solche Mikrooptimierung scheint im Allgemeinen schwierig zu sein.
Aber ... was ist, wenn sie keine Ints sind!
Ich habe angenommen, dass es sich um Ganzzahlen handelt, da die Indizes für die binäre Suche ganze Zahlen sind. Wenn sie tatsächlich keine Ganzzahlen sind, haben Sie einige Probleme damit, auf Arrays zuzugreifen. Aber in der Zwischenzeit können Sie verschiedene Ergebnisse erleben:
%Vor%Ähnlich,
%Vor%Das letztere Beispiel ist anders, auch wenn mir nicht klar ist, was besser ist. Warum dies der Fall ist, können Sie die Überlauf-Erklärungen in dem oben verlinkten Artikel betrachten.
Ich habe diese Frage bei Google durchsucht und eine sehr interessante Antwort auf Ссылка
Hier ist ein Beispiel:
%Vor%Der Fehler ist in dieser Zeile:
%Vor%Bei der Programmierung von Perlen sagt Bentley, dass die analoge Linie "m auf den Durchschnitt von l und u setzt, gekürzt auf die nächste ganze Zahl." Auf den ersten Blick scheint diese Behauptung korrekt zu sein, aber sie schlägt für große Werte der int Variablen niedrig und hoch fehl. Insbesondere schlägt es fehl, wenn die Summe von niedrig und hoch größer ist als der maximale positive int-Wert (231 - 1). Die Summe überläuft einen negativen Wert und der Wert bleibt negativ, wenn sie durch zwei geteilt wird. In C verursacht dies einen Array-Index außerhalb der Grenzen mit unvorhersagbaren Ergebnissen. In Java wird ArrayIndexOutOfBoundsException ausgelöst.
Dieser Fehler kann für Arrays auftreten, deren Länge (in Elementen) 230 oder größer ist (ungefähr eine Milliarde Elemente). Das war unvorstellbar in den 80er Jahren, als Programming Pearls geschrieben wurde, aber heutzutage bei Google und anderen Orten. In Programming Pearls sagt Bentley: "Während die erste binäre Suche 1946 veröffentlicht wurde, erschien die erste binäre Suche, die für alle Werte von n korrekt funktioniert, erst 1962." Die Wahrheit ist, dass nur wenige korrekte Versionen jemals veröffentlicht wurden, zumindest in gängigen Programmiersprachen.
Was ist der beste Weg, um den Fehler zu beheben? Hier ist eine Möglichkeit:
%Vor%Tags und Links python