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

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

+2

Оно?

→ Ответить

»

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

+5

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

→ Ответить

»

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

+1

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

→ Ответить

»

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

+25

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

→ Ответить

»

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

+26

Это ж CodeForces)

→ Ответить

»

AlTimin

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

+16

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

→ Ответить

»

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

-32

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

→ Ответить

»

AlTimin

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

0

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

→ Ответить

»

Fcdkbear

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

+8

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

→ Ответить

»

vanchope

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

← 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 функции.

→ Ответить

»

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

0

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

→ Ответить

»

vanchope

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

+16

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

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

или через long

→ Ответить

»

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

0

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

→ Ответить

»

vanchope

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

+3

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

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

→ Ответить

»

winger

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

+19

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

→ Ответить

»

dalex

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

← Rev. 2 →

-13

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

// пусть функция 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;
  }
}

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

→ Ответить

»

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

+34

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

→ Ответить

»

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

0

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

→ Ответить

»

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

← 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 в присваиваниях.

→ Ответить

»

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

← Rev. 2 →

-8

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

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

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

→ Ответить

»

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

0

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

→ Ответить

»

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

+10

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

→ Ответить

»

qwerty787788

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

← Rev. 2 →

+8

if (Check(L))

и return внутри while

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

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

→ Ответить

»

dalex

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

+8

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

→ Ответить

»

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

← Rev. 2 →

0

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

→ Ответить

»

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

0

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

→ Ответить

»

qwerty787788

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

+5

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

→ Ответить

»

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

+6

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

→ Ответить

»

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

+8

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

→ Ответить

»

tamir

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

0

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

→ Ответить

»

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

+3

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

→ Ответить

»

Fefer_Ivan

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

0

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

→ Ответить

»

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

+4

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

→ Ответить

»

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

+10

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

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

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

→ Ответить

»

yeputons

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

+10

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

→ Ответить

»

andrewzta

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

+3

Да.

→ Ответить

»

Perlik

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

+3

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

→ Ответить

»

cerealguy

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

+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 не происходит.

→ Ответить

»

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

+3

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

→ Ответить

»

Alex_2oo8

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

+5

Может я, конечно, что-то не понимаю, но зачем оставлять интервал длины 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

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

0

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

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

→ Ответить

»

Alex_2oo8

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

+5

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

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

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

→ Ответить

»

PavelKunyavskiy

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

← Rev. 2 →

+6

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

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

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

→ Ответить

»

Alex_2oo8

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

+8

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

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

→ Ответить

»

oops

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

← Rev. 3 →

+3

Вообще-то это общепринятый вариант реализации бин.поиска, используемый в 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 используется другой инвариант.

→ Ответить

»

Perlik

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

0

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

→ Ответить

»

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

← Rev. 3 →

-19

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

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;
    }

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

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;
    }

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

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

→ Ответить

»