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

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

整数上の二分探索

できること

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

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

計算量

$O(logN)$

使い方

auto [L, R] = binary_search([&](long long x){
    return 5 <= x;
});

Verified with

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

Code

#pragma once
#include <functional>
pair<long long, long long> binary_search(function<bool(long long)> f) {
    long long L = 0, R = 1, MID = 0;
    while (!f(R)) R <<= 1;
    while (abs(R - L) > 1) {
        MID = L + (R - L) / 2;
        (f(MID) ? R : L) = MID;
    }
    return {L, R};
}

#line 2 "library/search/binary_search/binary_search.hpp"
#include <functional>
pair<long long, long long> binary_search(function<bool(long long)> f) {
    long long L = 0, R = 1, MID = 0;
    while (!f(R)) R <<= 1;
    while (abs(R - L) > 1) {
        MID = L + (R - L) / 2;
        (f(MID) ? R : L) = MID;
    }
    return {L, R};
}

Back to top page