Этот вопрос был , только недавно заданный снова . Помимо цитаты Кнута о том, что «хотя основная идея бинарного поиска сравнительно проста, детали могут быть на удивление хитрыми», существует удивительный исторический факт (см. TAOCP, том 3, раздел 6.2.1), что бинарный поиск впервые был опубликован в 1946, но первый опубликованный бинарный поиск без ошибок был в 1962 году. И есть опыт Бентли, когда он назначал бинарный поиск на курсах для профессиональных программистов в таких местах, как Bell Labs и IBM, и давал им два часа, все сообщали они поняли это правильно, и при проверке кода 90% из них имели ошибки - год за годом.
Возможно, основная причина, по которой многие программисты допускают ошибки в бинарном поиске, помимо закона Стерджона, заключается в том, что они недостаточно внимательны: Программирование Pearls цитирует это как "напиши свой код, брось его поверх стену, и у нас есть контроль качества или тестирование с подходом к ошибкам ». И есть много возможностей для ошибки. Не только ошибка переполнения, о которой упоминают некоторые другие ответы, но и логические ошибки.
Ниже приведены некоторые примеры ошибок бинарного поиска. Это ни в коем случае не является исчерпывающим. (Как пишет Толстой в Анна Каренина - «Все счастливые семьи одинаковы; каждая несчастная семья по-своему несчастна» - каждая неправильная программа двоичного поиска неверна по-своему.)
Pattis
Следующий код Паскаля взят из статьи Ошибки учебника при бинарном поиске (1988) Ричарда Э. Паттиса. Он просмотрел двадцать учебников и предложил этот двоичный поиск (кстати, Паскаль использует индексы массивов, начиная с 1):
PROCEDURE BinarySearch (A : anArray,
Size : anArraySize,
Key : INTEGER,
VAR Found : BOOLEAN;
VAR Index : anArrayIndex);
Var Low, High : anArrayIndex;
BEGIN
LOW := 1;
High := Size;
REPEAT
Index := (Low + High) DIV 2;
If Key < A[Index]
THEN High := Index - 1
ELSE Low := Index + 1
UNTIL (Low > High) OR (Key = A[Index]);
FOUND := (Low <= High)
END;
выглядит хорошо? Это имеет более одной ошибки. Прежде чем читать дальше, посмотрите, сможете ли вы найти их все. Вы должны быть в состоянии угадать, что делает код, даже если вы впервые видите Pascal.
Он описывает пять ошибок, которые есть во многих программах, и, в частности, в приведенных выше:
Ошибка 1 : не выполняется за время O (log n), где n = размер. В своем увлечении правильной практикой программирования некоторые программисты пишут бинарный поиск как функцию / процедуру и передают ему массив. (Это не является специфическим для Паскаля; представьте, что в C ++ передача вектора осуществляется по значению, а не по ссылке.) Это - (n) время просто передать массив в процедуру, что наносит ущерб всей цели. Хуже того, некоторые авторы, по-видимому, дают рекурсивный бинарный поиск, который каждый раз пропускает массив, давая время выполнения, которое равно & Theta; (n log n). (Это не надумано; я действительно видел такой код.)
Ошибка 2 : сбой при размере = 0. Это может быть нормально. Но в зависимости от предполагаемого приложения, список / таблица, в которой выполняется поиск , может уменьшиться до 0, и его нужно где-то обработать.
Ошибка 3 : неверный ответ. Всякий раз, когда последняя итерация цикла начинается с Low = High (например, когда Size = 1), он устанавливает Found: = False, даже если Key находится в массиве.
Ошибка 4 : Вызывает ошибку всякий раз, когда Key меньше, чем наименьший элемент массива. (После того как Index становится 1, он устанавливает High в 0 и т. Д .; вызывает ошибку за пределами допустимого диапазона.)
Ошибка 5 : Вызывает ошибку всякий раз, когда Key больше, чем самый большой элемент массива. (После того, как Index станет Size, для Low будет задано значение Размер + 1 и т. Д .; возникнет ошибка за пределами допустимого диапазона.)
Он также указывает, что некоторые очевидные способы «исправить» эти ошибки также оказываются неверными. Реальный код также часто обладает этим свойством, когда программист пишет что-то неправильное, находит ошибку, а затем «исправляет» ее, пока она не покажется правильной, не подумав достаточно внимательно.
Из 20 учебников, которые он пробовал, только 5 имели правильный двоичный поиск. В оставшихся 15 (по иронии судьбы он говорит 16) он обнаружил 11 случаев ошибки 1, шесть случаев ошибки 2, по две ошибки 3 и 4 и одну ошибку 5. Эти цифры составляют в целом гораздо больше 15, потому что у нескольких из них было несколько ошибок.
Дополнительные примеры
Двоичный поиск используется не только для поиска в массиве, чтобы увидеть, содержит ли он значение, поэтому пока еще один пример. Я могу обновить этот список, как только подумаю.
Предположим, у вас есть возрастающая (неубывающая) функция f: R-> R, и (например, если вы хотите получить корень из f), вы хотите найти наибольшее t такое, что f(t) < 0. Посмотрите, сколько ошибок вы можете найти в следующем:
float high = INF, low = 0;
while(high != low) {
float mid = (low + high)/2;
if(f(mid)>0) high=mid;
else low=mid;
}
printf("%f", high);
(Некоторые: в [0, INF] может не быть такого t, если f равно 0 на интервале, тогда это неправильно, никогда не сравнивайте числа с плавающей запятой для равенства и т. Д.)
Как написать бинарный поиск
Раньше я делал несколько таких ошибок - первые несколько десятков раз я писал бинарный поиск (который был во время соревнований по программированию с нехваткой времени), примерно в 30% случаев где-то была ошибка - пока я не нашел простой способ написать это правильно. С тех пор я не ошибся в двоичном поиске (насколько я помню). Трюк очень прост:
Поддерживать инвариант.
Найдите / определите и сделайте явное некое инвариантное свойство, которому ваши «низкие» и «высокие» переменные удовлетворяют на протяжении всего цикла: до, во время и после. Убедитесь, что он никогда не нарушается. Конечно, вам также нужно подумать о состоянии прекращения. Это подробно объясняется в главе 4 Programming Pearls , которая выводит программу двоичного поиска из полуформальных методов.
Например, чтобы немного абстрагировать исследуемое условие, предположим, что вы хотите найти наибольшее целочисленное значение x, для которого выполняется некоторое условие poss(x). Даже такая явность определения проблемы - это больше, чем многие программисты начинают с. (Например, poss(x) может быть a[x] ≤ v для некоторого значения v; это узнать, сколько элементов в отсортированном массиве a больше, чем, скажем, v.) Затем один способ записи бинарный поиск:
int lo=0, hi=n;
//INVARIANT: poss(lo) is true, poss(hi) is false
//Check and ensure invariant before starting binary search
assert(poss(lo)==true);
assert(poss(hi)==false);
while(hi-lo>1) {
int mid = lo + (hi-lo)/2;
if(poss(mid)) lo = mid;
else hi = mid;
}
printf("%d \n",lo);
Вы можете добавить больше утверждений утверждений и других проверок, но основная идея заключается в том, что, поскольку вы обновляете lo до mid только , когда вы знаете, что poss(mid) является истинным, вы поддерживаете инвариант что poss(lo) всегда верно. Точно так же вы устанавливаете hi на mid только тогда, когда poss(mid) ложно, поэтому вы поддерживаете инвариант, что poss(hi) всегда ложно. Подумайте об условиях расторжения отдельно. (Обратите внимание, что когда hi-lo равно 1, mid совпадает с lo. Поэтому не пишите цикл как while(hi>lo), иначе у вас будет бесконечный цикл.) В конце цикла, вам гарантировано, что hi-lo не больше 1, и поскольку вы всегда сохраняете свой инвариант (poss(lo) - истина, а poss(hi) - ложь), оно не может быть 0. Кроме того, опять же из-за вашего инварианта вы знаете, что lo - это значение для возврата / печати / использования. Конечно, есть и другие способы написания бинарного поиска, но поддержание инварианта - это хитрость / дисциплина, которая всегда помогает.