Каковы подводные камни при реализации бинарного поиска?

Ответ 1

Вот некоторые из них, о которых я могу думать:

• Ошибки по очереди при определении границы следующего интервала
• Обработка повторяющихся элементов, если вы хотите вернуть первый равный элемент в массиве, но вместо этого возвратите следующий равный элемент
• Числовые переполнения/переполнения при вычислении индексов с огромными массивами
• Рекурсивная или нерекурсивная реализация, выбор дизайна, который вы должны рассмотреть

Это то, что вы имеете в виду?

Ответ 2

Этот вопрос был недавно еще раз спросил. Помимо цитаты Кнута: "Хотя основная идея бинарного поиска сравнительно проста, детали могут быть удивительно сложными", есть ошеломляющий исторический факт (см. TAOCP, том 3, раздел 6.2.1), что бинарный поиск был впервые опубликован в 1946 год, но первый опубликованный бинарный поиск без ошибок был в 1962 году. И есть опыт Bentley, когда он назначил бинарный поиск на курсах для профессиональных программистов в таких местах, как Bell Labs и IBM, и дал им два часа, все сообщили, что у них все получилось, и при рассмотрении их кода у 90% из них были ошибки - из года в год.

Возможно, основная причина, по которой так много программистов совершают ошибки с бинарным поиском, помимо Закона Стурджона, заключается в том, что они недостаточно осторожны: программирование Pearls цитирует это как "напишите ваш код, выбросьте его через стену и получите Quality Assurance или" Тестирование" с подходом к ошибкам. И есть много возможностей для ошибки. Не только ошибка переполнения, упоминаемая здесь в нескольких других ответах, но и логические ошибки.

Ниже приведены примеры ошибок двоичного поиска. Это отнюдь не является исчерпывающим. (Как пишет Толстой в "Анне Карениной" - "Все счастливые семьи одинаковы, каждая несчастная семья недовольна по-своему" - каждая неверная программа бинарного поиска неверна по-своему.)

Pattis

Следующий код Паскаля взят из статьи "Ошибки учебника в двоичном поиске" (1988) Ричарда Э Паттиса. Он посмотрел на двадцать учебников и придумал этот бинарный поиск (BTW, Pascal использует индексы массива, начиная с 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 = Размер. В своем энтузиазме к правильной практике программирования некоторые программисты пишут двоичный поиск как функцию/процедуру и передают ему массив. (Это не относится к Pascal, представьте, что в С++ передается вектор по значению, а не по ссылке.) Это время & Theta; (n) просто для того, чтобы передать массив процедуре, которая побеждает целую цель. Хуже того, некоторые авторы, по-видимому, дают рекурсивный двоичный поиск, который каждый раз передает массив, предоставляя время работы & theta; (n log n). (Это не надуманно, я действительно видел такой код.)

Ошибка 2: он не работает, когда size = 0. Это может быть нормально. Но в зависимости от предполагаемого приложения поиск в списке/таблице может уменьшаться до 0, и его нужно обрабатывать где-то.

Ошибка 3. Это дает неправильный ответ. Всякий раз, когда конечная итерация цикла начинается с Low = High (например, при Size = 1), он устанавливает Found: = False, даже если Key находится в массиве.

Ошибка 4: он вызывает ошибку, когда Key меньше наименьшего элемента массива. (После Index становится 1, он устанавливает High в 0 и т.д., Вызывает ошибку за пределами границ.)

Ошибка 5: она вызывает ошибку всякий раз, когда Key больше, чем самый большой элемент массива. (После Index становится Size, он устанавливает Low в Size + 1 и т.д., Вызывает ошибку за пределами границ.)

Он также указывает, что некоторые очевидные способы "исправить" эти ошибки также ошибочны. Реальный код также часто имеет это свойство, когда программист написал что-то неправильное, обнаружил ошибку, а затем "исправил" его, пока он не станет правильным, не подумав достаточно тщательно.

Из 20 учебников, которые он пытался, только 5 имели правильный бинарный поиск. В оставшихся 15 (по иронии судьбы он говорит 16), он обнаружил 11 экземпляров Error 1, шесть экземпляров Error 2, по два каждого из ошибок 3 и 4 и один из Error 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 "Программирование жемчуга", которая выводит двоичную программу поиска из полуформальных методов.

Например, чтобы немного абстрагироваться от проверяемого условия, предположим, что вы хотите найти наибольшее целочисленное значение 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);

Вы можете добавить несколько утверждений assert и других проверок, но основная идея состоит в том, что, поскольку вы обновляете lo до mid только тогда, когда знаете, что poss(mid) является истинным, вы сохраняете инвариант, что poss(lo) всегда правда. Точно так же вы устанавливаете hi в mid только тогда, когда poss(mid) является ложным, поэтому вы поддерживаете инвариант, что poss(hi) всегда false. Подумайте о состоянии завершения отдельно. (Обратите внимание, что когда hi-lo равно 1, mid совпадает с lo. Поэтому не записывайте цикл как while(hi>lo), или у вас будет бесконечный цикл.) В конце цикла, вам гарантировано, что hi-lo не больше 1, и потому что вы всегда поддерживали свой инвариант (poss(lo) is true и poss(hi) is false), он не может быть 0. Кроме того, опять же из-за вашего инварианта вы знаете, что lo - значение для возврата/печати/использования. Существуют и другие способы написания бинарного поиска, но сохранение инварианта - это трюк/дисциплина, которые всегда помогают.

Ответ 3

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

Ошибка - это целочисленное переполнение. Это не вызывало у людей проблем, потому что вряд ли кто-то искал достаточно большие структуры данных.

Ответ 4

Если у вас есть книга "Программирование жемчуга" рядом, вы должны проверить главу 4.

edit2: Как указано в комментариях, вы можете загрузить проект главы, на которой я упомянул сайт автора: http://www.cs.bell-labs.com/cm/cs/pearls/sketch04.html

Ответ 5

Невозможно считать, что при вычислении средней точки между двумя индексами суммирование высоких и низких значений может привести к переполнению целых чисел.

Ссылка

Ответ 6

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

Одно универсальное правило учится у неудачи. Здесь, размышления о "недействительных" случаях помогают прояснить проблему. Что делать, если ввод пуст? что, если ввод содержит дубликаты? следует ли его реализовать с помощью одного условного теста или двух тестов (плюс дополнительный тест для раннего завершения) на итерацию? и другие технические проблемы, такие как числовое переполнение/недополнение в вычислительных индексах и другие трюки.

Ошибки, которых можно было бы избежать, охарактеризовать проблему хорошо, это ошибки "по очереди" и обработка повторяющихся элементов, как отметил @Zach Scrivena.

Многие люди рассматривают двоичный поиск как нахождение целевого значения при сортированном массиве. Это как двоичный, как используется, а не бинарный поиск по сути.

Я попытаюсь дать относительное строгое определение/формулировку бинарного поиска и показать один способ выйти из-за ошибки и дублировать проблемы,, используя один конкретный подход, что, конечно, не ново.

# (my) definition of binary search:
input: 
    L: a 'partially sorted' array, 
    key: a function, take item in L as argument
prerequisite: 
    by 'partially sorted' I mean, if apply key function to all item of L, we get a 
    new array of bool, L_1, such that it can't be partitioned to two left, right blocks, 
    with all item in left being false, all item in right being true. 
    (left or/and right could be empty)
output: 
    the index of first item in right block of L_1 (as defined in prerequisite). 
    or equivalently, the index of first item in L such that key(item) == True

это определение, естественно, решает проблему с дублированием.

Обычно есть два способа обозначить массивы, [] и [), я предпочитаю последнее, подход эквивалентности [) использует вместо этого (start, count) пару.

# Algorithm: binary search
# input: L: a 'partially sorted' array, key: a function, take item in L as argument
    while L is not empty:
        mid = left + (right - left)/2  # or mid = left + count/2
        if key(mid item) is True:
            recede right # if True, recede right
        else:
            forward left # if False, forward left
    return left

Таким образом, если вы сделаете свой ", если True, Recede (end)" и ", если False, Forward (start)" , вы почти закончили. Я называю это "правилом FFTR" двоичного поиска.. Если вы собираетесь найти первый элемент, как в приведенном выше определении, левый будет запущен, однако право начнется, если вы собираетесь найти последний элемент. Я согласен с [) модой, тогда возможно реализовать,

while left<right:
    mid = left + (right - left)/2
    if key(L(mid)) == True:
        right = mid
    else:
        left = mid+1
    return left

позволяет проверить его далее, сперва показать конвергенцию, а затем показать правильность.

конвергенция:

whenever left == right, we exit loop (also true if being empty at the first)

so, in the loop, if denote, 

    diff = (right - left)/2, 

    lfstep = 1 + diff/2, 'lfstep' for 'left index forward step size'

    rbstep = diff - diff/2, 'rbstep' for 'right index back (recede) step size'

it can be show that lfstep and rbstep are alway positive, so left and right 
will be equal at last. 

both lfstep and rbstep are asymptotically half of current subarray size, so it 
of logarithm time complexity.

Корректность:

if the input array is empty:
    return the left index;
else:
    if key(mid item) is true:
        "recede right"
        so mid and all item after mid are all true, we can reduce the search range 
        to [left, mid), to validate it, there are two possible cases,
        case 1:
            mid is the first item such that key(item) is True, so there are no true items 
            in new search range [left, mid), so the test will always be false, and we 
            forward left at each iteration until search range is empty, that is  
            [finalleft,mid), since we return finalleft, and finalleft == mid, correctly done!
        case 2:
            there are item before mid such that key(item) is True,
            in this case we just reduce to a new problem of smaller size
    else:
        "forward left"
        mid and all item before mid is false, since we are to find the first true one, 
        we can safely reduce to new search range [mid+1, right) without change the result.

эквивалентная версия (начало, число),

while count>0:
    mid = start + count/2
    if key(L[mid]) == True:
        right = mid
    else:
        left = mid+1
return left

, чтобы суммировать, если это соответствует [),

1. define your key function of your problem, 
2. implement your binary search with "FFTR rule" -- 
    "recede (end) if True ( key(item) == True) else forward (start)" 
    examples:
        if to find a value target, return index or -1 if not found,
        key = lambda x: x>=target, 
        if L[found_index] == target: return found_index
        else: return -1

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

Ответ 7

Архитектура конвейерной обработки современных процессоров гораздо более подходит для линейных поисков, чем для бинарных поисков, которые имеют множество решений и ветвей.

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

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