Бинарная логика среднего значения

Question

Я рекурсивно написал бинарный поиск ??.При расчете среднего индекса я сделал int mid = (low + high) / 2.Я прогуглил рекурсивную версию бинарного поиска и обнаружил, что вычисление является ошибкой.Потому что он может переполниться, если (low + high) больше максимального значения целого числа.Есть два типа решений.

• int mid = low + (high - low) / 2
• int mid = (high + low) >>> 1 (беззнаковое смещение вправо, деление на 2)

Оба они работают как шарм.Тем не менее, мне интересно, как это работает.Да, это работает, но какая логика, что люди думают, чтобы найти это.Во-вторых, как это работает.Разве еще нет возможности переполниться для (high + low)?Я имею в виду, что моя попытка вызвана ошибкой из-за переполнения, но вторая также делает (high + low).???

Answer 1

В (high + low) >>> 1 все еще может быть подписанный перенос, но оператор >>> обрабатывает свой левый операнд как без знака , поэтому подписанный перенос не имеет значения.Этот подход работает, потому что unsigned wraparound: high и low не являются (как целые числа со знаком) неотрицательными, так что как целые числа без знака они не могут быть достаточно большими, чтобы вызвать обход без знака.

То, что добавление двух неотрицательных целых чисел со знаком никогда не страдает от обхода без знака, можно увидеть, сложив максимально возможные числа: 2 ^k-1 -1 + 2 ^k-1 -1 (где k - размер в битах целочисленного типа, обычно 32), что в сумме составляет 2 ^k -2.Это еще не все: наибольшее представимое число - 2 ^k -1.

Так что не «переполнение» в high + low действительно вызывает проблему, по крайней мере, вразумный язык, где безопасна арифметика со знаком, такая как Java.Последующая обработка результата high + low как целого числа со знаком гипотетической / 2, которая следует за ним, вызывает проблемы.

Answer 2

Предположим, что ваши целые числа имеют 16-разрядную подпись (просто для краткости; масштабируйте их, если вам нужны 32-разрядные целые числа).

Диапазон составляет -32768 ... 32767.

Пример, в котором low + (high - low) / 2 будет переполнен:

low = -20000
high = 30000
high - low = 50000 = (after overflow) -15536
(high - low) / 2 = -7768
low - (high - low) / 2 = -27768

Пример, в котором (high + low) >>> 1 будет переполнен:

low = -20000
high = -10000
low + high = -30000 = (binary) 1000101011010000
(low + high) >>> 1 = (binary) 0100010101101000 = 17768

Расчет среднего значения без какой-либо возможности переполнения неэффективен и может быть выполненнесколькими способами:

1. Сначала преобразуйте в более высокую «точность», например, 32-разрядный в 64-разрядный;преобразовать обратно после вычисления среднего

2. Разделить ваши числа на 2 и использовать какой-то "остаток"

   low2 = low >>> 1;
   high2 = high >>> 1;
   low_remainder = low & 1; // get the lowest significant bit
   high_remainder = high & 1; // get the lowest significant bit
   avg2 = low2 + high2; // this cannot overflow
   avg = avg2 + (low_remainder + high_remainder) / 2; // this cannot overflow
   

   Я не уверен, что этот точный код работает;это всего лишь идея.

3. Рассчитайте среднее значение обычным способом, а затем проверьте «неожиданный» результат (среднее значение меньше low или больше high).Если необычно, рассчитайте его «безопасным» способом.

4. Каким-то образом убедитесь, что ваш ввод не может вызвать переполнение.Это не работает для библиотек, но часто работает в реальных приложениях, где у вас есть верхняя граница, как 10000 для всех ваших чисел.Или может быть, ваши числа неотрицательны;тогда low + (high - low) / 2 фактически не может переполниться .

Answer 3

Причина первой работы

• математически идентично: l + (h - l)/2 = l + h/2 - l/2 = l/2 + h/2 = (l + h)/2, а
• из-за приоритета операций: сначала круглые скобки, затем деление на 2, затем сложение.

Достаточно забавно, но это "решение" может по-прежнему переполняться большим отрицательным low, поэтому оно не является решением вашей исходной проблемы.

Вы можете сделать что-то вроде low/2 + high/2, чтобы избежать переполнения, но вам нужно будет явно записывать вычисления для четных-четных (выше), четных-нечетных, нечетных-четных и нечетных-нечетных, чтобы остаться в int пространство При этом вы можете использовать >>>, чтобы избежать фактического разделения.