Вычисление среднего значения двоичного поиска

Ниже приведен псевдокод, полученный из учебника TopCoder о бинарном поиске

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

Почему мы вычисляем среднее значение как mid = lo + (hi-lo)/2? Что случилось с (hi + lo)/2

У меня есть небольшая идея, что это может быть предотвращение переполнения, но я не уверен, возможно, кто-то может объяснить это мне, и если есть другие причины этого.

Ответ 1

Да, (hi + lo)/2 может переполняться. Это была настоящая ошибка в реализации бинарного поиска Java.

Нет, для этого нет других причин.

Ответ 2

В дальнейшем в этом же учебнике:

"Вы также можете задаться вопросом, почему вычисление середины вычисляется с использованием mid = lo + (hi-lo)/2 вместо обычной mid = (lo + hi)/2. Это необходимо, чтобы избежать другой потенциальной ошибки округления: в в первом случае мы хотим, чтобы деление всегда округлялось вниз к нижней границе, но деление усекает, поэтому, когда lo + hi будет отрицательным, оно начнет округлять к верхней границе. Кодирование вычисления таким образом гарантирует, что число разделено всегда положителен и, следовательно, всегда округляется по мере того, как мы этого хотим. Хотя ошибка не возникает, когда пространство поиска состоит только из целых положительных чисел или действительных чисел, я решил закодировать его таким образом в статье для согласованности".

Ответ 3

Хотя этот вопрос составляет 5 лет, но есть статья отличная статья в googleblog, которая объясняет проблему и решение в деталях, что стоит поделиться.

Необходимо упомянуть, что в текущей реализации бинарного поиска в Java mid = lo + (hi - lo) / 2 расчет не используется, вместо этого быстрее и больше прозрачная альтернатива используется с оператором сдвига нулевой заливки

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

Ответ 4

Действительно возможно (hi+lo) переполнять целое число. В улучшенной версии может показаться, что вычитание lo из hi, а затем добавление его снова бессмысленно, но есть причина: выполнение этой операции не будет превышать целое число, и это приведет к числу с тем же parity как hi+lo, так что остаток (hi+lo)/2 будет таким же, как (hi-lo)/2. lo затем можно безопасно добавить после деления для достижения того же результата.