Вычисление середины в бинарном поиске - PullRequest
Новая
       12

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

30 голосов
/ 18 июля 2011

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

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."

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

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

Ответы [ 4 ]

43 голосов
/ 18 июля 2011

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

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.

5 голосов
/ 18 июля 2011

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

3 голосов
/ 25 июля 2015

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

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

2 голосов
/ 18 июля 2011

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

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

...