実数上の二分探索
(library/search/binary_search/binary_search_real.hpp)

• View this file on GitHub
• Last update: 2026-01-15 10:11:56+09:00
• Include: #include "library/search/binary_search/binary_search_real.hpp"

実数上の二分探索

できること

• 実数全体で二分探索し、L Rを返す
• 上界を指数探索で求めてる
• 3.5<=xならL=3.5, R=3.5(LRの誤差がEPS内)

     L R
   x x x o o o o
       ↑ここを求める
  

計算量

$O(logN)$

使い方

auto [L, R] = binary_search_real([&](double x){
    return 3.5 <= x;
});

Verified with

• 実数上の二分探索のテスト (tests/search.binary_search.binary_search_real.test.cpp)

Code

#pragma once
#include <functional>
const long double EPS = 1e-14;
pair<double, double> binary_search_real(function<bool(double)> f) {
    double L = 0, R = 1, MID = 0;
    while (!f(R)) R *= 2;
    auto ABS = [&]() { return abs(R - L) > EPS; };
    auto REL = [&]() { return abs(R - L) / max(R, L) > EPS; };
    while (ABS() and REL()) {
        MID = L + (R - L) / 2;
        (f(MID) ? R : L) = MID;
    }
    return {L, R};
}

#line 2 "library/search/binary_search/binary_search_real.hpp"
#include <functional>
const long double EPS = 1e-14;
pair<double, double> binary_search_real(function<bool(double)> f) {
    double L = 0, R = 1, MID = 0;
    while (!f(R)) R *= 2;
    auto ABS = [&]() { return abs(R - L) > EPS; };
    auto REL = [&]() { return abs(R - L) / max(R, L) > EPS; };
    while (ABS() and REL()) {
        MID = L + (R - L) / 2;
        (f(MID) ? R : L) = MID;
    }
    return {L, R};
}

Back to top page