Вычисление середины в двоичном поиске

Я читал книгу алгоритмов, которая имела следующий алгоритм для двоичного поиска:

public class BinSearch {
  static int search ( int [ ] A, int K ) {
    int l = 0 ;
    int u = A. length −1;
    int m;
    while (l <= u ) {
      m = (l+u) /2;
      if (A[m] < K) {
        l = m + 1 ;
      } else if (A[m] == K) {
        return m;
        } else {
          u = m−1;
        }
       }
       return −1;
      }
 }

Автор говорит: "Ошибка в присваивании m = (l+u)/2; может привести к переполнению и должна быть заменена на m = l + (u-l)/2."

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

Итак, в каких случаях произойдет переполнение?

Ответ 1

Этот пост широко описывает эту знаменитую ошибку. Как говорили другие, это проблема переполнения. Исправление, рекомендуемое по ссылке, выглядит следующим образом:

int mid = low + ((high - low) / 2);

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

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

(low < 0 && high > 0) ? (low + high) / 2 : low + (high - low) / 2

может потребоваться. Хорошим примером является поиск медианы в несортированном массиве без его модификации или использование дополнительного пространства, просто выполняя двоичный поиск в целом Integer.MIN_VALUE - Integer.MAX_VALUE.

Ответ 2

Проблема заключается в том, что сначала оценивается (l+u) и может переполнять int, поэтому (l+u)/2 вернет неправильное значение.

Ответ 3

Джефф предложил действительно хороший post, чтобы прочитать об этой ошибке, вот резюме, если вы хотите быстрый обзор.

В программировании жемчуга Бентли говорит, что аналогичная линия "устанавливает m в среднее значение l и u, усекается до ближайшего целого". На первый взгляд это утверждение может показаться правильным, но оно терпит неудачу при больших значениях переменных int, низких и высоких. В частности, он терпит неудачу, если сумма низких и высоких превышает максимальную положительную величину int (2 ^ 31 - 1). Сумма переполняется до отрицательного значения, а значение остается отрицательным при делении на два. В C это приводит к тому, что индекс массива выходит за пределы с непредсказуемыми результатами. В Java он выдает исключение ArrayIndexOutOfBoundsException.

Ответ 4

Потенциальное переполнение происходит в самом добавлении l+u.

На самом деле ошибка в ранних версиях двоичного поиска в JDK.

Ответ 5

Ответ прост: дополнение l + u может переполниться и имеет неопределенное поведение в некоторых языках, как описано в блоге Джошуа Блоха об ошибке в библиотеке Java для реализации бинарного поиска.

Некоторые читатели могут не понимать, о чем речь:

l + (u - l) / 2

Обратите внимание, что в некотором коде имена переменных различаются, и это

low + (high - low) / 2

Ответ таков: скажем, если у вас есть два числа: 200 и 210, а теперь вам нужно "среднее число". И скажем, если вы добавите любые два числа, и результат будет больше 255, тогда он может переполниться и поведение не определено, тогда что вы можете сделать? Простой способ - просто добавить разницу между ними, но только половину, к меньшему значению: посмотрите, какая разница между 200 и 210. Это 10. (Вы можете считать это "разницей" или "длиной"). ", между ними). Так что вам просто нужно добавить 10 / 2 = 5 к 200 и получить 205. Вам не нужно сначала добавлять 200 и 210 вместе - и вот как мы можем достичь вычисления: (u - l) - это разница. (u - l) / 2 это половина. Добавьте это к l, и мы получим l + (u - l) / 2.

Чтобы представить это в исторической перспективе, Роберт Седжвик упомянул, что первый двоичный поиск был упомянут в 1946 году, и он был неправильным до 1964 года. Джон Бентли описал в своей книге "Программирование жемчужин" в 1988 году, что более 90% профессиональных программистов не могли написать правильно, учитывая пару часов. Но даже сам Джон Бентли имел эту ошибку переполнения в течение 20 лет. Исследование, опубликованное в 1988 году, показало, что точный код для бинарного поиска был найден только в 5 из 20 учебников. В 2006 году Джошуа Блох написал в своем блоге сообщение об ошибке при вычислении значения mid. Таким образом, потребовалось 60 лет, чтобы этот код был правильным. Но теперь, в следующий раз на собеседовании, не забудьте написать его правильно в течение этих 20 минут.