Практически все реализации двоичного поиска и сортировки слиянием не работают!
Если вы не знаете, что такое двоичный поиск: это алгоритм поиска, который использует парадигму Divide & Conquer для поиска целевого элемента в отсортированном массиве с помощью O (log n) временная сложность, где 'n' - размер массива.
Все программисты очень часто пользуются бинарным поиском!
Вот две реализации двоичного поиска на C ++ с разницей в всего одну строку, расположенные рядом:
Оба алгоритма используют переменную mid для:
- прекратить поиск, если целевое значение найдено в текущей
midposition. - уменьшите пространство поиска, сравнив значение в
midposition с целевым значением, разделив массив на две половины и, следовательно, выполняя поиск в левой или правой половине.
Вы заметили разницу в строке 6?
Итак, у нас есть два способа вычисления mid:
Но какая разница? Вы запускаете его на тоннах тестовых примеров, сделанных вручную, и он все равно дает правильный ответ, БЕЗ ГАРМОНИИ. . .
Да, да, вы поняли! Когда сумма low и high превысит 2³¹!
Во-первых, давайте разберемся, как он будет переполняться:
Предположим, у вас есть массив размером 2³¹-1 (максимальное значение, которое может содержать 32-битное целое число со знаком), который содержит элементы от 1,2,3 .. до 2³¹-1 в порядке возрастания. Допустим, target (элемент для поиска) равен 2³¹-2 (последний второй элемент):
[1,2,3, .. .. .. ,2³¹/2, .. .. .. .. ,(2³¹-3),(2³¹-2),(2³¹-1)]
mid target
На первой итерации вы вычисляете
mid = (0 + 2³¹ — 1)/2.
mid и target можно увидеть ниже:
[1,2,3, .. .. .. ,2³¹/2, .. .. .. ,(2³¹-3),(2³¹-2),(2³¹-1)] low mid target high
Однако, поскольку target (2³¹ -2 ) находится в правой половине массива, мы устанавливаем
low = mid + 1
Итак, пространство поиска сокращается до 2-й половины массива:
[2³¹/2 + 1, .. .. .. , (2³¹-3), (2³¹-2), (2³¹-1)] low target high
Теперь, во второй итерации, мы вычисляем новое mid как :
mid = ( (2³¹/2 + 1) + 2³¹ -1)/2
приводит к переполнению, поскольку общая сумма превышает 2³¹. Это может привести к непредсказуемым результатам. (См. Трассировку выполнения ниже)
Это была знаменитая ошибка переполнения двоичного поиска, которая оставалась незамеченной более 20 лет !!!
Даже двоичный поиск Java в java.util.Arrays имел ошибку та же ошибка, пока о ней не сообщили в Sun Microsystems и не исправили в 2006 году.
Итак, как исправить ошибку?
Мы уже видели:
int mid = low + ((high - low) / 2);
Более быстрый способ сделать это (в данном конкретном случае):
int mid = (low + high) >>> 1;
где >>> - беззнаковый оператор сдвига вправо.
В C / CPP, где >>> недоступен, можно использовать следующее:
mid = ((unsigned int)low + (unsigned int)high)) >> 1;
Ошибка двоичного поиска в равной степени относится и к сортировке слиянием, и к другим алгоритмам «разделяй и властвуй». Поэтому было бы разумно исправить реализации кода, если вы не знали об этом.
Во-вторых, мы что-то упустили? Что упускают из виду большинство блогов? Прагматический анализ.
Из всей шумихи по поводу знаменитой ошибки переполнения двоичного поиска в исследовательском блоге Google и многих других блогах упускается одна вещь:
«Разрешено ли размещать массив размером 2³¹? Может ли такая проблема возникнуть в реальных системах? »
Распределение памяти:
Обратите внимание, что для целочисленного массива размером 2³¹ потребуется 8 ГиБ памяти.
Для Java:
Оказывается, вы можете создать массив размером 2³¹ - 1 (или достаточно большим для возникновения условия переполнения).
Для C ++:
Конечно, вы не можете выделить такой объем памяти статически в стеке (вы получите ошибку времени выполнения, которая приведет к сбою вашей программы из-за превышения размера стека по умолчанию, обычно 1–8 МБ), но вы может выделить столько памяти в куче. Таким образом, в C ++ все еще может возникать ошибка переполнения.
Теоретически, что, если размер массива составляет ›2³¹, скажем, 2³². Что ж, в этом случае вам нужно будет использовать 64-битные целые числа, и снова то же самое условие приведет к 2⁶³ и так далее. На самом деле массивы таких размеров обычно не являются предпочтительными из-за последующей проблемы размещения их в памяти.
Таким образом, в зависимости от использования и размера систем в наши дни, вполне возможно, что такой случай может возникнуть. Следовательно, рекомендуется писать свои реализации алгоритмов Divide and Conquer (например, двоичного поиска) с учетом таких условий.
В двух словах:
- Все алгоритмы Divide and Conquer уязвимы для подобных ошибок.
- Исправьте свои реализации, особенно если они являются частью библиотеки и, следовательно, могут получать входные данные неожиданно большого размера.
Нажмите «ПОДПИСАТЬСЯ» ниже, чтобы бесплатно получать статьи из The Bit Theories на ваш почтовый ящик.
Хлопайте ниже, чтобы повысить эту статью.
Вам также может понравиться:
Хотите присоединиться к нашей замечательной команде авторов? См. Ниже:
