Бинарный поиск знаком по нахождению элемента в отсортированном массиве. В олимпиадных задачах он часто применяется иначе: неизвестен оптимальный ответ, но можно быстро проверить, допустимо ли конкретное значение. Чтобы такой поиск работал, результаты проверки должны меняться монотонно. Именно доказательство монотонности важнее запоминания короткого цикла с двумя границами.
От ответа к проверяемому вопросу
Представим, что требуется разместить три точки в разрешенных позициях 1, 2, 4, 8, 9 и сделать минимальное расстояние между выбранными точками как можно большим. Вместо прямого поиска оптимума зададим вопрос: можно ли разместить точки так, чтобы расстояние между соседними выбранными позициями было не меньше d?
Если размещение возможно для d = 3, оно подходит и для любого меньшего положительного расстояния. Если для d = 5 размещение невозможно, увеличение расстояния не поможет. Поэтому значения d делятся на допустимую и недопустимую части. Для приведенных позиций оптимум равен трем: подходят точки 1, 4, 8, а расстояние четыре уже обеспечить нельзя.
Почему проверка тоже требует доказательства
Для фиксированного d можно идти слева направо и выбирать ближайшую разрешенную позицию после предыдущей. Выбор самой ранней подходящей позиции оставляет следующей точке не меньше пространства справа. Так обосновывается жадная проверка, а не только ее правдоподобие на рисунке.
Если процедура проверки неверна, бинарный поиск лишь быстрее приведет к неверному ответу. Поэтому сначала проверьте ее отдельно на небольших примерах. В другой задаче допустимость может требовать динамического программирования, обхода графа или расчета количества изготовленных изделий. Бинарный поиск не определяет способ проверки автоматически.
Как договориться о границах
Удобно хранить два значения: заведомо допустимое lo и заведомо недопустимое hi. Пока между ними есть целое число, проверяем середину. При успехе передвигаем lo, при неуспехе hi. Перед циклом нужно объяснить, почему начальные границы действительно обладают указанными свойствами.
Другой шаблон может искать первое истинное значение вместо последнего. Оба подхода допустимы, но их нельзя смешивать. Запишите словами смысл каждой переменной и условие завершения. Для целочисленного поиска особенно внимательно проверьте соседние границы, единственный возможный ответ и случай, когда допустимых значений нет.
Как оценить скорость
Число проверок растет логарифмически от длины диапазона. Если одна проверка проходит по n элементам, итоговая сложность составляет O(n log R), где R характеризует диапазон поиска. Дополнительную сортировку, если она нужна, учитывают отдельно. Большой диапазон значений не равен большому числу элементов.
В Олимпиадных школах МФТИ есть направление олимпиадной информатики. При выборе подготовки полезно искать разборы, в которых объясняют корректность проверки и границ, а не только показывают готовую реализацию.
Что записать после решения
Оставьте три коротких доказательства: монотонности, правильности проверки и сохранения смысла границ. Затем сравните программу с полным перебором на маленьких данных. Такая проверка помогает отделить ошибку в модели от ошибки на единицу в коде и делает бинарный поиск инструментом для новых задач.
