Бинарный поиск

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Здравствуй, сообщество Кодефорсес!

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

int l = xxx, r = xxx; // здесь инициализация границ

while (xxx) {// пока условие, зависящее от границ 
    int m = f(l, r); // середина - какая-то функция от левой и правой границ

    if (check(m))  // это я знаю!!!
        l = f1(m); // мы каким-то образом меняем левую границу
    else
        r = f2(m); // мы каким-то образом меняем правую границу
}

//здесь вывод/возвращение/использование ответа (тоже непонятного)

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

В общем, будьте добры, кому не лень, скинуть правильную, рабочую, не зацикливающуюся версию бинарного поиска.

Спасибо за внимание!

// пусть функция check сначала возвращает false, а потом true // найдем самое маленькое значение, для которого true int left, right, ans; while (left <= right) { int mid = (left + right) / 2; if (check(mid)) { ans = mid; right = mid - 1; } else { left = mid + 1; } }

template<typename _ForwardIterator, typename _Tp, typename _Compare> _ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __val, _Compare __comp) { typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType; // concept requirements __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>) __glibcxx_requires_partitioned_lower_pred(__first, __last, __val, __comp); _DistanceType __len = std::distance(__first, __last); while (__len > 0) { _DistanceType __half = __len >> 1; _ForwardIterator __middle = __first; std::advance(__middle, __half); if (__comp(*__middle, __val)) { __first = __middle; ++__first; __len = __len - __half - 1; } else __len = __half; } return __first; }

template<typename _ForwardIterator, typename _Tp> _ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __val) { typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType; // concept requirements __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) __glibcxx_requires_partitioned_lower(__first, __last, __val); _DistanceType __len = std::distance(__first, __last); while (__len > 0) { _DistanceType __half = __len >> 1; _ForwardIterator __middle = __first; std::advance(__middle, __half); if (*__middle < __val) { __first = __middle; ++__first; __len = __len - __half - 1; } else __len = __half; } return __first; }

Комментарии (49)

Показать архивные | Написать комментарий?

Rubanenko

11 лет назад, # |

Оно?

→ Ответить

BekzhanKassenov

11 лет назад, # ^ |

А где будет храниться ответ?

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

+25

Интересно, а за что вас заминусовали?

+26

Это ж CodeForces)

AlTimin

+16

За "еще один вызов проверяющей функции ни на что не влияет" в приличном обществе бьют по лицу мокрой тряпкой.

-32

А потом с бревнами сидят эти тряпочные бойцы :о)

Как раз с бревнами сидят люди, действующие по принципу "Какой такой инвариант, слушай? Да что ты несешь, нужно просто плюс-минус один добавить. Ну еще и в этом месте. Ну вот еще одну проверку добавлю — точняк заработает"

Fcdkbear

Туториал на топкодере

vanchope

← Rev. 4 →

-10

В своё время пришёл к такому варианту:

		int a = Leftmost_possible;
		int b = Rightmost_possible;
		while( a <= b){
			int mid = (a+b)/2;
			if (possible(mid)){
				b = mid-1;
			}else{
				a = mid+1;
			}
		}
		return a;

Единственное, надо убедиться, что mid вычисляется без integer overflow.

UPD. Такой вариант работает для монотонно возрастающей boolean функции.

А если все же переполняется?

тогда можно попробовать

    int mid = a + (b-a)/2;

или через long

При таком варианте все остальные условия сохраняются?

в ответе будет минимальный индекс, для которого функция возвращает true. зацикливания нет.

предполагается, что хотя бы f(R) = true, иначе на всём интервале будет false.

winger

+19

int mid = a/2 + b/2 + (a&b&1);

dalex

← Rev. 2 →

-13

У меня раньше были с этим проблемы, пока я не начал писать так (не помню уже, у кого подсмотрел):

Если надо найти что-то иное, этот код очень просто изменить, и очевидно, как это сделать (т.е. либо строчку ans = mid переставить в другую ветку if-а, либо присваивания left и right поменять местами).

HAPKOMAH

+34

Не знаю как все, но я всегда отрезки делаю "[;)", ибо так гораздо проще с границами.

А подробнее можно?

NikitaPogodin

← Rev. 3 →

+29

Отредактировал.

int L = minValue, R = maxValue + 1;
while (R - L > 1)
{
   int M = (L + R) / 2;
   if (Check(M))
      L = M;
   else
      R = M;
}
return L;

Код вернет в L последнее M, в котором Check истинно. Если необходимо получить первое неистинное M, то можно брать L + 1 с проверкой на выход за пределы или искать с помощью R. Плюсы этого подхода — нет лишних +1 и -1 в присваиваниях.

-8

А я, пожалуй, упрощу твой код из первой правки:

return Check(minValue) ? (minValue + maxValue + 1) / 2 : minValue;

UPD: мог бы и не редактировать, за тебя все cerealguy отредактировал.

Я сначала прочитал комментарии к своему посту, отредактировал, а потом увидел его пост. Впрочем, очевидно же, что я имел в виду в начале.

+10

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

qwerty787788

if (Check(L))

и return внутри while

Этот комментарий набрал 14 плюсов?

UPD. теперь ок, только если Check(minValue) != true, то ответ будет не верным и его нужно будет отдельно проверять.

Никто не заметил

Я тоже не заметил :) Но все поняли, я надеюсь.

Да, но, насколько я понимаю, его в любом случае придется проверять для случая, когда весь отрезок false, какой бы мы поиск не писали. Например, для открытого интервала придется проверять, не равен ли L -1.

Если сам Check пишется в три строчки, то выделять его в отдельную функцию как-то странно (особенно когда Check использует локальные переменные и их придется передавать в функцию). Тогда в твоем варианте придется эти три строчки написать два раза. А если писать с открытым интервалом, то проверка на равенство minValue -1 всегда занимает одну строчку.

Справедливое замечание. Впрочем, я всегда выделяю Check в отдельную функцию, если он занимает больше одной строчки.

На самом деле все меня учат делать отрезки "(;)", ибо так еще проще с границами и правильней, но я так не делаю.

tamir

Почитай здесь ( http://habrahabr.ru/post/91605/) . Должно помочь )

Омг, какой же там срач развели на эту тему... Это все прочитать — уже проблема :)

Fefer_Ivan

Чтобы не думать об условиях останова при вещественном бинпоиске можно вместо цикла while(xxx) написать цикл for(int i = 0; i < 100; ++i). Однако, для целочисленного поиска лучше сделать наоборот. А именно while(right - left > 5) делать бинпоиск, а оставшиеся несколько элементов перебрать циклом for(int mid = left; mid <= right; ++mid).

Самая легко запоминающаяся идея :) Скорее всего так и буду делать

Да, и если кому интересно, условия останова в вещественном бинпоиске:

double mid = (left + right) * .5;
while (mid != left && mid != right) {
  if (check(mid))
    right = mid;
  else
    left = mid;
  mid = (left + right) * .5;
}

но я так тоже не делаю.

yeputons

Интересный вариант. А почему это адекватно работает с большими числами? Неужели всегда выполняется a ≤ (a + b) * 0.5 ≤ b (не сарказм)?

andrewzta

Да.

Perlik

Можно еще писать не совсем бинарный поиск, а что-то вроде двоичного подъема. Работает тоже за лог, но если, например, поиск идет по массиву, то кеш вроде используется намного эффективнее. Именно так работает lower_bound в C++. Ищет на отрезке [l;r), при неудачном поиске возвращает r.
Код

cerealguy

+130

20 комментариев и ни одного нормального бинпоиска.

Ближе всех NikitaPogodin, но и он сделал три бага.

Правильный бинпоиск:

int L = minValue - 1, R = maxValue + 1;
while (R - L > 1) {
    int M = (L + R) / 2;
    if (check(M)) {
        R = M;
    } else {
        L = M;
    }
}
return {L,R}

Инвариант: для $\text{[math]}$ check(x) == false, для $\text{[math]}$ check(x) == true.
Ответ хранится одновременно в L и R, которые после работы алгоритма отличаются на один.
Можно заметить, что обращений к minValue - 1 и maxValue + 1 не происходит.

Два бага, просто мой поиск немного отличается (там в пояснении описано). Пожалуй, ваш вариант немного удобней, да.

Alex_2oo8

Может я, конечно, что-то не понимаю, но зачем оставлять интервал длины 1? Если мы проверили, что M не подходит в качестве ответа, то ответ >M и соответственно можно исключить M из интервала:

int L = minValue, R = maxValue;
while (L < R) {
    int M = (L + R) / 2;
    if (check(M)) {
        R = M;
    } else {
        L = M + 1;
    }
}
return L;

PavelKunyavskiy

Такой вариант не отработает в случае, когда maxValue достигается. А если они еще и отрицательные, то когда L = R-1 выберется R, и вернется какая-то полная чушь. Кроме того, оно видимо не так легко перенесется на случай "найти последний false"

В принципе сам я пишу так, как описан NikitaPogodin. В чем преимущество того, что написал Миша над этим в упор не понимаю.

Все таки, если мы ищем минимальное подходящее число и таковым является maxValue, то такой вариант его найдет. На последней итерации L = R - 1; M = L и потом, так как M нам не подходит, L = M + 1 = R.

В случае же с отрицательными числами проблема только в строчке int M = (L + R) / 2;, которую можно заменить на int M = L + (R - L) / 2;

На счет найти последний false — найдем первый true и отнимем единицу?

Ну я не совсем это имел ввиду. Допустим мы хотим найти первый >= или последний <=.

А так видимо даже действительно работает.

P.S Понятно, что это все полечится +-1 куда-то там. Речь как раз про то, чтобы написать максимально так, чтобы их не возникало.

На последний <= переносится не сложно :)

PS +-1 есть во всех приведенный реализациях (в том числе в первой строке), но, видимо, каждому удобнее по-своему.

oops

Вообще-то это общепринятый вариант реализации бин.поиска, используемый в STL. Вариант cerealguy нестандартный, хотя в нем проще запомнить внутреннюю часть цикла, но нужно не забыть как правильно установить начальные L и R (то, что легко можно ошибиться показал NikitaPogodin)

При поиске в массиве R должен быть номером первого элемента за верхней границей массива, т.е. ищем в диапазоне [L;R)

Здесь инвариант цикла check(L-1)==false && check(R)==true. Если помнить инвариант, то легко сообразить, где нужно добавить +1. Аналогично инвариант поможет правильно установить начальные L и R в варианте cerealguy.

PS Если minValue беззнаковый, то границу L в варианте cerealguy невозможно инициализировать правильно при minValue=0, поэтому в STL используется другой инвариант.

Вообще-то в STL такого бинпоиска нет (хотя бы потому что итераторы не поддерживают /2). В STL используется такой вариант.

-19

Про STL — вот код, найденный в файле stl_algo.h:

Этот — в файле stl_algobase.h:

P.S: Используется MinGW

UPD: А минусы-то за что?

Я не ошибся в начальных значениях, всегда писал его именно так. Из минусов, как уже обсудили выше — отдельный Check после выхода из поиска.

Sammarize

+18

Это, однозначно, самый полезный комментарий во вселенной, серьёзно.

Блог пользователя BekzhanKassenov