Ich suche nach einer effizienten Formel, die in Java arbeitet und den folgenden Ausdruck berechnet:
%Vor%wird für die binäre Suche verwendet. Bisher habe ich "low + (high - low) / 2" und "high - (high - low) / 2" verwendet Überlauf und Unterlauf in einigen Fällen zu vermeiden, aber nicht beides. Jetzt suche ich nach einem effizienten Weg, dies zu tun, was für jede Integer-Zahl der Fall wäre (vorausgesetzt, die Ganzzahlen reichen von -MAX_INT - 1 bis MAX_INT).
UPDATE : Ich kombinierte die Antworten von Jander und Peter G. und experimentierte eine Weile mit den folgenden Formeln für das Element mit mittlerem Wert und seine unmittelbaren Nachbarn:
Niedrigster Mittelpunkt (gleich floor((low + high)/2) , z.B. [2 3] - & gt; 2, [2 4] - & gt; 3, [& ndash; 3 -2] - & gt; -3)
Höchster Mittelpunkt (gleich ceil((low + high)/2) , beispielsweise [2 3] - & gt; 3, [2 4] - & gt; 3, [& ndash; 3 -2] - & gt; -2)
Vor-Mittelpunkt (gleich floor((low + high - 1)/2)) , z.B. [2 3] - & gt; 2, [2 4] - & gt; 2, [& ndash; 7 -3] - & gt; -6)
Nach-Mittelpunkt (gleich ceil((low + high + 1)/2)) , beispielsweise [2 3] - & gt; 3, [2 4] - & gt; 4, [& ndash; 7 -3] - & gt; -4)
Oder, ohne bitweise und (& amp;) und oder (()), etwas langsamer Code ( x >> 1 kann durch floor(x / 2) ersetzt werden, um bitweise Operator-freie Formeln zu erhalten):
Am weitesten links-Mittelpunkt
%Vor%Ganz rechts-Mittelpunkt
%Vor%Vorher-Mittelpunkt
%Vor%Nach-Mittelpunkt
%Vor% Hinweis : Der obige Operator >> wird als signierte Verschiebung betrachtet.
Von Ссылка :
%Vor%ist ein überlaufsicherer Durchschnitt von zwei Ganzzahlen ohne Vorzeichen.
Nun funktioniert dieser Trick nur bei unsignierten Ganzzahlen. Aber weil ((a+x) + (b+x))/2 = (a+b)/2 + x , können Sie es wie folgt täuschen, wenn Sie Integer mit der gleichen Bitgröße wie Ihre Ganzzahlen mit Vorzeichen haben:
UPDATE : Wenn Sie darüber nachdenken, funktioniert das auch, wenn Sie keine Ganzzahlen mit Vorzeichen haben. Bitweise, vorzeichenbehaftete und vorzeichenlose Ganzzahlen sind über Additions-, Subtraktions- und Boolesche Operationen äquivalent. Also müssen wir uns nur darum kümmern, dass die Division wie eine Division ohne Vorzeichen wirkt, was wir tun können, indem wir eine Verschiebung verwenden und das oberste Bit ausblenden.
%Vor% (Beachten Sie, dass Sie bei Verwendung von Java eine nicht signierte Schicht, ... >>> 1 , anstelle von (... >> 1) & MAX_INT verwenden können.)
JEDOCH gibt es eine Alternative, über die ich gestolpert bin, die noch einfacher ist, und ich habe noch nicht herausgefunden, wie es funktioniert. Es ist nicht notwendig, die Zahlen mit MAX_INT anzupassen oder vorzeichenlose Variablen oder irgendetwas zu verwenden. Es ist einfach:
%Vor% Getestet mit allen Kombinationen von vorzeichenbehafteten 16-Bit-Ganzzahlen low und high im Bereich -32768..32767, aber noch nicht bewiesen (von mir sowieso).
Unter der Annahme high >= low sollte auch eine Variante Ihres ersten Ansatzes funktionieren:
wobei >>> eine vorzeichenlose Verschiebung ist (wie in Java).
Die Idee ist, dass high - low niemals überläuft, wenn das Ergebnis als vorzeichenlose Ganzzahl interpretiert wird, so dass die vorzeichenlose Verschiebung die Division korrekt um 2 durchführt und die Formel den mittleren Wert berechnet.
Tags und Links java math integer overflow binary-search