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

Da die vorzeichenlose Rechtsverschiebung in der Go-Programmierung nicht vorhanden ist, können wir zur Vermeidung eines Integer-Überlaufs bei der Berechnung des Mittelwerts in der Go-Programmiersprache wie folgt schreiben.

mid := int(uint(lo+hi) >> 1)

Answer 2

Die Frage nach dem Warum ist beantwortet, aber es ist nicht leicht zu verstehen, warum die Lösung funktioniert. Nehmen wir also an, 10 ist hoch und 5 ist niedrig. Nehmen wir an, dass 10 der höchste Wert ist, den eine ganze Zahl haben kann (10+1 würde einen Überlauf verursachen).

Anstatt also (10+5)/2 7 zu machen (weil 10 + irgendetwas zu einem Überlauf führen würde).

Wir machen 5+(10-5)/2=> 5 + 2,5 7