в чем разница между mid=(beg+end)/2 и mid=beg+(end-beg)/2 в бинарном поиске?

Может быть, второй может избежать переполнения.

Точно. Нет никакой гарантии, что beg+end представим; но во втором случае промежуточные значения, как и ожидаемый результат, не превышают end, поэтому опасности переполнения нет.

Вторая форма также может использоваться для аффинных типов, таких как указатели и другие итераторы произвольного доступа, которые можно вычесть, чтобы получить расстояние, но не сложить вместе.

В общем случае оба выражения неверны. Например, первое выражение неверно, потому что нет такой операции, как + для указателей или итераторов. Второе выражение некорректно, если используются итераторы неслучайного доступа. Например, когда используются двунаправленные итераторы.

Таким образом, правильная конструкция в C++ будет выглядеть следующим образом.

mid = std::next( beg, std::distance( beg, end ) / 2 );

Если мы рассмотрим две строки в более общем контексте, не связанном с бинарным поиском, можно сделать следующие наблюдения:

Вы правы в том, что вторая форма пытается избежать проблемы переполнения, пытаясь представить число, большее, чем максимальное представимое число.

Нет никаких ограничений на то, насколько велики отдельные числа beg и end, поэтому потенциально они оба могут быть больше половины максимального представимого числа. Их добавление означает, что промежуточный результат (beg+end) может переполниться.

Второе решение, кажется, устраняет риск переполнения, но вводит еще один. Если значения являются значениями со знаком, их разница может снова переполниться (или потерять значение, в зависимости от их знаков). Беззнаковые значения не имеют проблем.

Есть еще одно решение, которое вы не опубликовали:

mid = beg/2 + end/2

Это решает все проблемы с переполнением и потерей значимости, но вводит новую проблему потери точности. При работе с целочисленными значениями деление на 2 может дать результат, равный 0,5, а сложение их вместе означает, что mid может отличаться на 1:

mid = 3/2 + 5/2; // mid is 3, instead of the 4 expected

Работа со значениями с плавающей запятой имеет и другие проблемы с точностью.

Возвращаясь к рассматриваемой проблеме, бинарному поиску, легко увидеть, что beg и end являются беззнаковыми значениями, поэтому второе решение всегда будет давать правильный результат.

Ответ в книге:

«Поскольку итератор, возвращаемый из конца, не обозначает элемент, он не может быть увеличен или разыменован».

Графически это имеет смысл как асимметричный диапазон, [начало, вне конца) или полуоткрытый диапазон.

Из Accelerated C++, стр. 28, Koenig.