Мне эта оптимизация помогла сдать задачу C из этого соревнования на 100 баллов: https://mirror.codeforces.com/gym/103631 Но скорее всего эта оптимизация будет значительно ускорять код, если проверка в бинарном поиске работает за быструю асимптотику или с хорошей константой. Тогда выгоднее сделать ее два раза, чем заново проходиться по запросам (у меня в этой задаче использовалось дерево Фенвика, и отрезок поиска делился на 4). Но вообще очень прикольно)

Гениален

Очень интересная идея. Простая программа а-ля Монте-Карло, показывает, что чем ближе пропорция деления к 0 (или к 1), тем меньше матожидание для количества шагов. И похоже, отношение матожидания с пропорцией, близкой к 0, к стандартной, с пропорцией 0.5 будет что-то около 0.80

Не все так просто, подобные методы не очень хорошо сокращают ожидаемое количество check'ов.

Про это была задача на opencup в 2016 году, там надо было угадать число за $$$\log_2 (n+1) + 0.1$$$ запросов в среднем (жюри играло честно и фиксировало число до начала игры, но игра повторялась $$$10\,000$$$ за тест). Эту задачу сдало ноль команд.

У Petr есть два блога про неё:

1. Почему эта задача не такая простая: https://petr-mitrichev.blogspot.com/2016/04/a-doubles-week.html?m=1

2. Решение: https://petr-mitrichev.blogspot.com/2016/04/a-binary-week.html?m=1

Все оказалось ну очень интересно. Предварительные прикидки с использованием, естественно, теории вероятностей и случайных процессов, показывают, что при уменьшении пропорции почти до нуля выигрыш (чисто с точки зрения матожидания) растет неограниченно (или я ошибаюсь??). На практике (то есть программа Монте-карло) получается константа чуть меньше 0.8. Где истина, попробую разобраться. И еще — при практическом применении этой идеи нам надо просто уменьшить длину интервала в K раз. И, естественно, нас в первую очередь будет волновать, чтобы в 99.999 процентах случаев это работало. Тут надо, очевидно, исследовать обычное, а не предельное распределение этого самого числа шагов. И тут, скорее всего, эту самую пропорцию надо брать ну никак не предельно близкую к нулю.

Автор, можете пояснить? Я вот прочитал текст уже три раза и ничего не могу понять. Как бинпоиску может помочь, что мы делимся не пополам?

В частности, да, $$$\frac{4}{9} < \frac{1}{2}$$$, но мы это получили не бесплатно: мы умножили длину отрезка на $$$\frac{4}{9}$$$ за две операции, а не за одну. Если бы мы сделали две операции нормального бинпоиска, умножили бы длину отрезка на $$$\frac{1}{4} < \frac{4}{9}$$$. Так в чём выгода?