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

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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

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

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

mid = beg/2 + end/2

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

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

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

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

Ответ 4

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

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

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

Из ускоренного С++, стр. 28, Koenig.