binary_search
(Optimization/binary_search.hpp)

• View this file on GitHub
• Last update: 2026-11-04 14:46:41+09:00
• Include: #include "Optimization/binary_search.hpp"

概要

めぐる式二分探索ㅤ |ok - ng| = 1 となるような (ng, ok) を見つけて、そのときの ok を返す

• binary_search_01(ng, ok, f)
• binary_search_10(ok, ng, f)

制約

• f(ng) = False
• f(ok) = True

問題例

• 競プロ典型 90 問 001 - Yokan Party（★4）

参考文献

• drken: 二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜

Required by

• template.hpp

Verified with

• tests/yukicoder_705_general_li_chao_tree.test.cpp
• tests/kyopro_tenkei_001.cpp (manual)

Code

#pragma once
#include <bits/stdc++.h>
using namespace std;

// binary search
template<class T, class FUNC> T binary_search_01(T ng, T ok, const FUNC &f) {
    while (abs(ok - ng) > 1) {
        T mid = ok + ng >> 1;
        if (f(mid)) ok = mid;
        else ng = mid;
    }
    return ok;
}
template<class T, class FUNC> T binary_search_10(T ok, T ng, const FUNC &f) {
    return binary_search_01(ng, ok, f);
}

#line 2 "Optimization/binary_search.hpp"
#include <bits/stdc++.h>
using namespace std;

// binary search
template<class T, class FUNC> T binary_search_01(T ng, T ok, const FUNC &f) {
    while (abs(ok - ng) > 1) {
        T mid = ok + ng >> 1;
        if (f(mid)) ok = mid;
        else ng = mid;
    }
    return ok;
}
template<class T, class FUNC> T binary_search_10(T ok, T ng, const FUNC &f) {
    return binary_search_01(ng, ok, f);
}

Back to top page