Binärsuche Mittelwertberechnung

Question

Der folgende Pseudocode stammt aus einem TopCoder-Tutorial über binäre Suche

binary_search(A, target):
   lo = 1, hi = size(A)
   while lo <= hi:
      mid = lo + (hi-lo)/2
      if A[mid] == target:
         return mid            
      else if A[mid] < target: 
         lo = mid+1
      else:
         hi = mid-1

   // target was not found

Warum berechnen wir den mittleren Wert als Mitte = lo + (hi - lo) / 2 ? Was stimmt nicht mit (hoch + niedrig) / 2

Ich habe die leise Vermutung, dass damit ein Überlauf verhindert werden soll, aber ich bin mir nicht sicher. Vielleicht kann mir jemand erklären, warum das so ist und ob es noch andere Gründe dafür gibt.

Answer 1

Diese Frage ist zwar schon 5 Jahre alt, aber es gibt eine großartiger Artikel im Googleblog die das Problem und die Lösung im Detail erklärt, was es wert ist, geteilt zu werden.

Es ist zu erwähnen, dass die derzeitige Implementierung der binären Suche in Java mid = lo + (hi - lo) / 2 Berechnung wird nicht verwendet, stattdessen wird die schnellere und klarere Alternative mit dem Null-Füll-Rechtsverschiebungs-Operator verwendet

int mid = (low + high) >>> 1;

Answer 2

Ja, (hi + lo) / 2 kann überlaufen. Dies war ein tatsächlicher Fehler in der Implementierung der binären Suche in Java.

Nein, es gibt keine anderen Gründe dafür.

Answer 3

Später im gleichen Lehrgang:

"Sie fragen sich vielleicht auch, warum die Mitte mit Mitte = lo + (hi-lo)/2 statt mit der üblichen Mitte = (lo+hi)/2 berechnet wird. Damit soll ein weiterer möglicher Rundungsfehler vermieden werden: Im ersten Fall soll die Division immer nach unten, zur unteren Grenze hin, abrunden. Die Division schneidet jedoch ab, so dass sie, wenn lo+hi negativ wäre, zur oberen Grenze hin abrunden würde. Wenn man die Berechnung auf diese Weise kodiert, wird sichergestellt, dass die geteilte Zahl immer positiv ist und daher immer so gerundet wird, wie wir es wollen. Obwohl der Fehler nicht auftritt, wenn der Suchraum nur aus positiven ganzen Zahlen oder reellen Zahlen besteht, habe ich beschlossen, ihn aus Gründen der Konsistenz im gesamten Artikel so zu kodieren."

Answer 4

Es ist in der Tat möglich, dass (hi+lo) zum Überlauf der Ganzzahl. In der verbesserten Version mag es so aussehen, als sei es sinnlos, lo von hi zu subtrahieren und dann wieder zu addieren, aber es gibt einen Grund dafür: Die Durchführung dieser Operation führt nicht zu einem Überlauf von integer y ergibt sich eine Zahl mit der gleichen Parität als hi+lo , so dass der Rest von (hi+lo)/2 ist dasselbe wie (hi-lo)/2 . lo kann dann sicher nach der Division addiert werden, um das gleiche Ergebnis zu erhalten.

Answer 5

Gehen wir davon aus, dass das Array, in dem wir suchen, die Länge INT_MAX hat. Daher zunächst:

high = INT_MAX 
low = 0

In der ersten Iteration stellen wir fest, dass das Zielelement größer ist als das mittlere Element und verschieben daher den Startindex nach Mitte als

low = mid + 1

In der nächsten Iteration, wenn die Mitte berechnet wird, wird sie als (hoch + niedrig)/2 berechnet was im Wesentlichen bedeutet, dass INT_MAX + low(which is half of INT_MAX + 1 ) / 2

Der erste Teil dieser Operation, d.h. (high + low), würde zu einem Überlauf führen, da wir den maximalen Int-Bereich, d.h. INT_MAX, überschreiten.