#algo

Бинарный поиск -- чуть ли не первый алгоритм, который мы узнаем.
Ну я по крайней мере.
Я его увидел когда-то Грокаем алгоритмы, а потом на спор угадывал число одноклассника от 1 до 4kkk за 32 попытки (не получилось: т.к. я считал в уме, погрешность вычислений в голове привела меня к отрезку длиной 8 на последнюю попытку; получил заслуженный фофан).

Потом мне рассказали про бинарный поиск по ответу.
Это когда у вас ответ на задачу -- монотонная функция.
Можно попробовать разные значения и понять, в какой момент она меняет значение (поиск квадратного корня или 371C как хорошие примеры).

Потом я думал про условный тернарный поиск, чтобы отсекать сразу 2/3 ответов, а не половину. Ничего не придумал.
Он используется, но в других местах.

Недавно попался доклад на P99 про ускорение бинарного поиска, но перед ним надо посмотреть на другой.

Оптимизируем бинарный поиск Сергея Слотина с C++ Zero Cost Conf 2022 (english версия с CppCon того же года; рекомендую её, т.к. в неё чуть больше поместилось).

Оптимизировать бинпоиск по Сергею Слотину это:
👍 избавляться от сложнопредсказуемого бранча
👍 префетчить потенциальные куски памяти
😎 менять memory layout, например с помощью Eytzinger нумерации
🤓 уходить в B-tree like укладывание элементов (S-tree)
🤔 улучшать с помощью B+-tree like оптимизации (S+-tree)

А на P99 был доклад от Ragnar Groot про докручивание решения выше, только на Rust.

Отойдя в сторону, есть вариация бинарного поиска, известная под названием Shar's algorithm, когда вместо поддержания двух границ вы сдвигаете индекс на степень двойки.
Тут прикольная статья про то, как автор генерировал код на D для решения задачи на массивах статического размера.
Некоторое развитие и на C++ есть у другого автора.

Во всех ресурсах выше речь идёт о классическом бинпоиске, а не о решении задачи с такими условиями.

Как говорил Сергей в докладе, есть и другие варианты.
Например, для маленького множества ключей можно заранее предпосчитать ответ на каждый возможный запрос и хранить их в lookup table (LUT) (для 8-16 байтовых типов это делается быстро и не очень дорого по памяти).
Если типы пошире, можно изменить вид LUT и в старших битах хранить границы более узкого отрезка, что позволяет изначально сокращать задачу бинпоиска на несколько итераций.
Подробнее это описано тут.

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

И не прям про бинпоиск, но под руку попался доклад, на который ссылаются разные бинпоиск статьи, хотя там рассказываются в целом общие идеи и корутины: Gor Nishanov «Nano-coroutines to the Rescue! (Using Coroutines TS, of Course)».

Рядом упомянем и другие вариации:
- exponential search для больших размеров
- fibonacci search для старых архитектур, т.к. там нужно только сложение и вычитание -> выполняется быстрее
- jump search, в котором минимизируется кол-во скачков назад (нужно только мамонтам имхо)
- fractional cascading позволяет оптимизировать задачу нахождения одного числа в нескольких массивах

И раз мы считаем среднее между двумя числами, вот доклад про std::midpoint. Там не всё так просто!

Я так и не научился за секунду писать бинописк правильно.
То единичку забуду, то про инвариант не подумаю.
Коварен.

Есть что-то добавить по теме?