Рубрики

Проблема во многих реализациях бинарного поиска

Рассмотрим следующую реализацию функции двоичного поиска на языке C, в этом что-то не так?

// Итеративная функция двоичного поиска. Возвращает местоположение х в
// заданный массив arr [l..r], если присутствует, иначе -1

int binarySearch(int arr[], int l, int r, int x)

{

    while (l <= r)

    {

        // найти индекс среднего элемента

        int m = (l+r)/2;

  

        // Проверяем, присутствует ли х в середине

        if (arr[m] == x) return m;

  

        // Если х больше, игнорируем левую половину

        if (arr[m] < x) l = m + 1;

  

        // Если х меньше, игнорируем правую половину

        else r = m - 1;

    }

  

    // если мы доберемся сюда, то элемента нет

    return -1;

}

Вышесказанное выглядит хорошо, за исключением одной тонкой вещи, выражения «m = (l + r) / 2». Сбой при больших значениях l и r. В частности, он терпит неудачу, если сумма минимума и максимума больше, чем максимальное положительное значение int (2 31 — 1). Сумма переполняется до отрицательного значения, и значение остается отрицательным при делении на два. В C это приводит к выходу индекса массива за границы с непредсказуемыми результатами.

Как решить эту проблему?
Ниже приводится один из способов:

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

Вероятно, быстрее, и, возможно, так же ясно (работает только в Java, см. Это ):

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

В C и C ++ (где у вас нет оператора >>>), вы можете сделать это:

        mid = ((unsigned int)low + (unsigned int)high)) >> 1 

Подобная проблема появляется и в Merge Sort .

Вышеуказанный контент взят из блога Google Reasearch .

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

Вышеуказанная проблема возникает, когда длина массива составляет 2 30 или более, и поиск повторно перемещается во вторую половину массива. Такой большой размер массива вряд ли появится большую часть времени. Например, когда мы пробуем приведенную ниже программу с 32-битным компилятором Code Blocks , мы получаем ошибку компилятора.

int main()

{

    int arr[1<<30];

    return 0;

}

Выход:

error: size of array 'arr' is too large

Даже когда мы пробуем логический массив, программа прекрасно компилируется, но вылетает при запуске в Windows 7.0 и 32-битном компиляторе Code Blocks

#include <stdbool.h>

int main()

{

    bool arr[1<<30];

    return 0;

}

Вывод: ошибки компиляции нет, но происходит сбой во время выполнения.

Источники:
http://googleresearch.blogspot.in/2006/06/extra-extra-read-all-about-it-nearly.html
http://locklessinc.com/articles/binary_search/

Эта статья предоставлена Абхай Рати . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Проблема во многих реализациях бинарного поиска

0.00 (0%) 0 votes