Как выглядит типичный бинарный поиск в вещественных числах? Так:

float l = 0.0f, r = 1e14f;
for (int i = 0; i < iteration_count && l + eps < r; ++i)
{
    float mid = 0.5f * (l + r);
    if (check(mid))
        r = mid;
    else
        l = mid;
}

Здесь l и r — границы, выставляемые исходя из условия, check(x) — функция, которая начиная с какого-то x возвращает true, до него — false, и нужно найти этот x. Как правило, l или 0.5 * (l + r) — ответ.

Но есть несколько минусов:

1. Количество итераций еще нужно подобрать, балансируя между точностью ответа и временем работы.
2. Ответ с погрешностью.

Что можно с этим сделать?

Для начала разберемся, как представляются вещественные числа. Детально можно почитать, к примеру, тут и тут. Воспользуемся тем, что если проделать операцию Y = real(int(X) + 1), где X — вещественоое число, int(X) принимает вещественное число и вовзращает целое, побитовое представление которого такое же, как у Х (то есть, возвращает тот же Х, но интерпретируемый как целое число), real(X) делает противоположное — интерпретирует целое как вещественное, то Y будет равен следующему представимому вещественному числу после Х. Грубо говоря, это аналогично Y = X + eps, где eps минимально возможный и X >= 0 и Y = X - eps, если X <= 0 (в обоих случаях включен ноль, потому что в вещественных числах есть и 0, и -0). Грубо — потому что не для всех Х одинаковый eps. Должен отметить, что есть NaN, inf, максимальное положительное или отрицательное число, но это не то, о чем я хочу говорить. Можно заметить, что для вещественных L и R, где L < R, выполняется условие int(L) < int(L) + 1 < int(L) + 2 < ... < int(R), аналогично как L < L + eps < L + 2 * eps < ... < R. Значит, можно делать бинарный поиск с границами int(L), int(R). Теперь мы умеем так:

float l_real = 0.0f, r_real = 1e14f;
uint32_t l = reinterpret_cast<uint32_t&>(l_real), r = reinterpret_cast<uint32_t&>(r_real);
while (l < r)
{
    uint32_t mid = l + (r - l) / 2;
    if (check(reinterpret_cast<float&>(mid)))
        r = mid;
    else
        l = mid + 1;
}

То же самое работает для double и uint64_t. Можно использовать int для float и long long для double. Должен отметить, что стандартом не гарантировано, что float и int по 32 бита, а double и long long — по 64 бита, но я не встречался с тем, чтоб это было не так.

Какие плюсы?

1. Максимально возможная точность.
2. Малое количество итераций (до 32 для float и до 64 для double).

Что важно помнить?

• l, r и mid — какие-то не несущие смысл числа, все что важно — сохранение порядка в обоих интерпретациях.
• l + r может переполниться, поэтому l + (r - l) / 2 вместо (l + r) / 2.
• Есть неудобство с границами с разными знаками. Для отрицательных чисел нужно перевести значение из прямого в дополнительный код при переводе из вещественного в целое, чтоб сохранить порядок. Так же можно сделать сначала проверку в нуле, чтоб у границ был одинаковый знак, или прибавить к значениям константу. На моем опыте, задач, где границы с разными знаками, крайне мало.

Не будет лишним рассмотреть картинки с распределением вещественных чисел на коородинатное прямой. Для примера, отмечу, что на отрезке от 0 до std::numeric_limints<float>::max() медиана (она же и первый mid в бинарном поиске) будет равна 1.5. То есть, от 0 до 1.5 представимо столько же чисел, сколько и от 1.5 до максимально представимого. Для float в обычном подходе понадобится 129 итераций только для того, чтоб правая граница стала меньше 1.5, если ответ, к примеру, 0 (не стоит забывать, что обычно в задачах начальная правая граница значительно меньше). То есть, в обычном подходе представимые значения отбрасываются крайне плохо.

Пример решения задачи, используя такой подход: 45343644

Такой же подход применим и к тернарному поиску (кто хочет сделать классный пример? ^_^).