В общем недавно появилось время и я доделал дерево вместо кучи,
померял и даже на простом компараторе получил ускорение на 15%.

Ещё недавно пофиксил оптимизировал довольно забавный кейс:
Дана сортированная по возрастанию последовательность уникальных чисел.
Затем по ней много ищут.
Есть две особенности:
1. В последовательности множество dense подотрезков, как правило с длиной больше 1.
2. Если все искомые числа выписать в одну последовательность, то это будет последовательность сортированных подотрезков, как правило с длиной больше 1.

Понятно что baseline здесь это обычный бинпоиск.
Но мы могли бы сохранить найденную позицию в массив.
Тогда при следующем поиске, нужно вычислить разницу между значением, которое было на этой позиции и искомым числом.
После прибавить эту разницу к прошлой позиции.
Затем проверить, что мы не вышли за пределы массива и это действительно искомый элемент.
В случае если между текущим искомым числом и прошлым был dense диапазон, мы нашли новое число.
А если не получилось все ещё можно использовать обычный бинпоиск.

Я не особо усердно бенчмаркал, так как это очевидно лучше, но даже на достаточно маленьких массивах (1e5) вышло в 2-4 раза быстрее.