Also richtig rechnen mid in einer binären Suche ist mid = low + ((high - low) / 2) um Überlauffehler zu behandeln.
Meine Implementierung verwendet vorzeichenlose 64-Bit-Variablen, und ich sehe nie eine Situation, in der meine Arrays so groß werden, dass sie einen Überlauf verursachen. Muss ich die obige Implementierung noch verwenden oder kann ich sie verwenden? mid = (low + high) / 2
Was ist hier die beste Vorgehensweise?
Wenn es keine Überlaufmöglichkeit gibt, ist die überlaufsichere Methode zur Berechnung des Mittelpunkts technisch unnötig: Sie können die unsichere Formel verwenden, wenn Sie möchten. Es ist jedoch wahrscheinlich eine gute Idee, es trotzdem dort zu lassen, falls Ihr Programm eines Tages modifiziert wird, um Ihre Annahmen zu brechen. Ich denke, dass das Hinzufügen einer einzigen CPU-Anweisung, um Ihren Code zukunftssicher zu machen, eine großartige Investition in die Wartbarkeit Ihres Codes ist.
Außerdem: Sie wissen nie, wann jemand Ihren Code ausschneiden und einfügen und an anderer Stelle verwenden wird, wo Ihre Annahmen nicht greifen. Vielleicht werden sie es auf einem 32-Bit-Rechner ausführen und riesige Arrays verwenden – oder so etwas. Wenn Sie eine Programmiersprache kennen, die stets funktioniert, ersetzen Sie es nicht durch eines, das gelegentlich funktioniert, es sei denn, es gibt einen guten Grund. (Besser als ein paar Tastenanschläge oder 2 Maschinenbefehle in einer Schleife zu sparen) nur meine 0,02 $
– JVMATL
13. Januar 2014 um 21:10 Uhr
Dabo
Überprüfen Sie diesen Artikel Fast alle binären Suchen und Mergesorts sind defekt
Bessere Praxis (für heute)
Wahrscheinlich schneller und wohl genauso klar ist: 6: int mid = (low + high) >>> 1;
und danach :
In C und C++ (wo Sie den >>>-Operator nicht haben) können Sie Folgendes tun: 6: mid = ((unsigned int)low + (unsigned int)high)) >> 1;
Und am Ende :
Update 17. Februar 2008: Danke an Antoine Trux, Principal Member of Engineering Staff am Nokia Research Centre Finland für den Hinweis, dass die ursprünglich vorgeschlagene Lösung für C und C++ (Zeile 6) nicht garantiert nach dem relevanten C99-Standard (INTERNATIONAL STANDARD – ISO/IEC – 9899 – Zweite Ausgabe – 1999-12-01, 3.4.3.3), die besagt, dass das Ergebnis undefiniert ist, wenn Sie zwei vorzeichenbehaftete Größen addieren und einen Überlauf erhalten. Der ältere C-Standard C89/90 und der C++-Standard sind beide in dieser Hinsicht identisch mit C99. Jetzt, da wir diese Änderung vorgenommen haben, wissen wir, dass das Programm korrekt ist;)
Fazit: Es wird immer einen Fall geben, in dem es nicht funktioniert
Codierer
Die Methode von Don Knuth funktioniert perfekt durch eine Bitmaske ohne die Möglichkeit eines Überlaufs:
return (low & high) + ((low ^ high) >> 1)
BEARBEITEN: low + high = (low ^ high) + (low & high) << 1
Seite 19, The Art of Computer Programming, Bd. 4, Donald E. Knuth
Also richtig rechnen
midin einer binären Suche istmid = low + ((high - low) / 2)um Überlauffehler zu behandeln.
Das ist falsch. In Betracht ziehen low = 18 * pow(10, 18) und high = 1 * pow(10, 18). Beide mid = (low + high) / 2 und Ihre Methode überläuft, ergibt 276627963145224192 statt richtig 9500000000000000000.
@EdHeal Ich denke, dass diese algebraisch und sogar mit eingerechneter Rundung gleich sind.
– Vorlagentypdef
13. Januar 2014 um 20:55 Uhr
@EdHeal Ich entschuldige mich, wenn ich etwas vermisse, aber kommen diese nicht in beiden Fällen gleich heraus?
– Vorlagentypdef
13. Januar 2014 um 21:22 Uhr
low + (high - low) / 2ist auch nicht garantiert sicher. Ich arbeite an Code, der negative Indizes unterstützt. Ein positiveshighund negativlowüberlaufen könntehigh - low.– Eric Postpischil
13. Januar 2014 um 21:43 Uhr