Почему эта реализация двоичного поиска вызывает переполнение

Question

В реализации бинарного поиска

int search(int[] A, int K) {
  int l = 0;
  int u = A.length - 1;
  int m
  while ( l <= u ) {
     m = (l+u)/2; // why this can cause overflow
     ...
  }
}

Правильный метод выглядит следующим образом:

m = l + (u -l )/2;

Я не знаю, почему в обновленном операторе нет проблемы переполнения.Насколько я понимаю, рано или поздно обновленное заявление также будет иметь проблему переполнения.

Спасибо

Answer 1

Орнал может иметь переполнение, поскольку l+u может быть больше максимального значения, которое может обработать int (например, если l и u были INT_MAX, то их сумма, очевидно, превысила бы INT_MAX).

Правильный метод не может переполниться, потому что u-l явно не переполнится, а l+(u-l)/2 гарантированно будет <=u, поэтому переполнение также не может.