Вещественный бинарный поиск: по числу итераций или по eps — что надёжнее на олимпиаде?
Решаю задачу, где ответ — вещественное число (например, найти точку, где монотонная функция f(x) = 0). Делаю while (hi - lo > 1e-9). На некоторых тестах TLE или WA по точности. Как правильно: по eps или по фиксированному числу итераций?
2 ответа
На олимпиадах почти всегда надёжнее фиксированное число итераций, а не условие hi - lo > eps. Причины:
while (hi - lo > eps)может зациклиться или работать неопределённо долго, если из-за погрешности double разность перестаёт уменьшаться ниже eps (например, при больших значениях, где машинный эпсилон самого числа больше твоего eps). С итерациями цикл гарантированно конечен.- Каждая итерация делит интервал пополам, то есть даёт ~1 бит точности. 100 итераций → диапазон сужается в 2^100 раз — это покрывает любую разумную точность с гигантским запасом. Обычно хватает 100–200 итераций.
double lo = 0, hi = 1e9; // границы по условию
for (int it = 0; it < 200; it++) {
double mid = (lo + hi) / 2;
if (f(mid) <= 0) lo = mid; // f возрастает, ищем корень
else hi = mid;
}
// ответ ~ lo (или hi, они почти совпали)
Сложность O(iters * cost(f)). Точность ответа ~ (hi0 - lo0) / 2^iters. При 200 итерациях это далеко за пределами точности double, так что лишние итерации бесплатны по точности, но проверь, что cost(f) не сделает TLE: если f дорогая, бери 100 итераций — этого уже достаточно для 1e-9.
Нюанс: не бери слишком большой hi от балды. Если интервал [0, 1e18], то 100 итераций дают абсолютную точность ~1e18/2^100 ≈ 1e-12 — норм. Но из-за конечной мантиссы double (~15-16 значащих цифр) при значениях порядка 1e9 ты физически не получишь больше ~1e-6 абсолютной точности около этих значений. Поэтому если в задаче требуется относительная точность, а числа большие — иногда лучше long double, либо переформулировать в целочисленный бинпоиск, домножив на масштаб. И не сравнивай результат через ==: сравнивай с допуском.