Berechnung der Mitte bei der binären Suche

Question

Ich habe ein Buch über Algorithmen gelesen, das den folgenden Algorithmus für die binäre Suche enthielt:

public class BinSearch {
  static int search ( int [ ] A, int K ) {
    int l = 0 ;
    int u = A. length 1;
    int m;
    while (l <= u ) {
      m = (l+u) /2;
      if (A[m] < K) {
        l = m + 1 ;
      } else if (A[m] == K) {
        return m;
        } else {
          u = m1;
        }
       }
       return 1;
      }
 }

Der Autor sagt: "Der Fehler liegt in der Zuordnung m = (l+u)/2; kann es zu einem Überlaufen kommen und sollte ersetzt werden durch m = l + (u-l)/2 ."

Ich kann mir nicht vorstellen, wie das zu einem Überlauf führen soll. Wenn ich den Algorithmus in meinem Kopf für ein paar verschiedene Eingaben laufen lasse, sehe ich nicht, dass der Wert der Mitte aus dem Array-Index herausgeht.

In welchen Fällen würde der Überlauf also auftreten?

Answer 1

Diese Antwort gibt ein praktisches Beispiel dafür, warum die l + (r-l)/2 Berechnung erforderlich ist.

Falls Sie neugierig sind, wie die beiden mathematisch gleichwertig sind, hier ist der Beweis. Der Schlüssel ist die Addition 0 und dann die Aufteilung in l/2 - l/2 .

(l+r)/2 =
l/2 + r/2 =
l/2 + r/2 + 0 =
l/2 + r/2 + (l/2 - l/2) =
(l/2 + l/2) + (r/2 - l/2) =
l + (r-l)/2

Answer 2

Der potenzielle Überlauf liegt in der l+u Zusatz selbst.

Dies war eigentlich ein Fehler in frühen Versionen der binären Suche im JDK.

Answer 3

Eigentlich die folgende Aussage in der Berechnung mid kann dazu führen, dass INT range Überlauf.

mid = (start + end) /2

Angenommen, die gegebene geordnete Eingabeliste ist sehr groß und übersteigt die INT range(-2^31 to 2^31-1) . Die start + end kann zu einer Ausnahme führen. Um dem entgegenzuwirken, wird die folgende Anweisung geschrieben:

mid = start + (end-start)/2

Letztendlich kommt es auf denselben Ausdruck an. Aber die Ausnahme wird durch diesen Trick abgewendet.

Answer 4

Denn wenn wir addieren: [ mid = low + high ] und sowohl mid als auch high groß sind, kann ihre Addition außerhalb des Bereichs der ganzen Zahl liegen

auch warum es nicht [ Mitte = niedrig/2 + hoch/2 ] ist, weil es sich um eine ganzzahlige Division handelt. Wenn also [ niedrig = 5 und hoch= 11 ] dann ist [ Mitte = niedrig/2 + hoch/2 ] Mitte = 5/2 + 11/2 => 2+ 5 => 9 Das führt zu einer falschen Antwort. Deshalb wird Mitte = niedrig + (hoch - niedrig)/2 genommen;

Answer 5

int mid=(l+h)/2; kann zu einem Integer-Überlaufproblem führen.

(l+u) wird zu einem großen negativen ganzzahligen Wert ausgewertet und seine Hälfte wird zurückgegeben. Wenn wir nun nach einem Element in einem Array suchen, würde dies würde dies zu einem "index out of range error" führen.

Das Problem wird jedoch wie folgt gelöst:-

• int mid=l+(h-l)/2;
• Bit-Manipulation: Für schnellere Berechnungen-> int mid=((unsigned int)l+(unsigned int)h) >> 1 ;

wobei >> der Rechtsverschiebungsoperator ist.

Ich hoffe, das hilft :)