二分探索 (Other/binary_search.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-07-18 00:30:04+09:00
• Include: #include "Other/binary_search.hpp"

二分探索

めぐる式二分探索により、与えられた条件を満たす境界値を求める関数です。 条件関数 check は単調性を仮定しています。

bin_search (integer)

template <typename T>
enable_if_t<is_integral_v<T>, T>
bin_search(T ok, T ng, function<bool(T)> check)

区間 [ok, ng) もしくは (ng, ok] において、

• check(ok) = true

• check(ng) = false

を満たす初期値を与えると、最終的に以下を満たす境界値を返します。

• 戻り値 ret は常に条件を満たします (check(ret) = true)。

• 隣の値 ret + 1 または ret - 1 は常に条件を満たしません (check(ret ± 1) = false)。

計算量

• $O(\log \mid ok - ng \mid)$

bin_search (float)

template <typename T>
enable_if_t<is_floating_point_v<T>, T>
bin_search(T ok, T ng, function<bool(T)> check, T precision = 1e-9)

区間 [ok, ng) または (ng, ok] において、浮動小数点数の探索を行います。 最終的に以下を満たす境界値 n を返します。

• check(n) = true, check(n + precision) = false

もしくは

• check(n - precision) = false, check(n) = true

つまり、条件が変化する境界を精度 precision 内で判定します。

計算量

• $O\left(\log\left(\frac{\mid ok - ng\mid}{\text{precision}}\right)\right)$

Required by

• k乗根（整数） (Math/kth_root_integer.hpp)
• Tree/lowest_common_ancestor.hpp

Verified with

• test/DataStructure/nth_accumulater/abc300-f.cpp
• test/Math/kth_root_integer/yosupo-kth_root_integer.cpp
• test/Other/binary_search/yukicoder-0067.cpp
• test/Tree/lowest_common_ancestor/aoj-GRL_5_C.cpp
• test/Tree/lowest_common_ancestor/yosupo-lca.cpp

Code

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

template <typename T>
enable_if_t<is_integral_v<T>, T>
bin_search(T ok, T ng, function<bool(T)> check)
{
    while (max(ok, ng) - min(ok, ng) > 1)
    {
        T mid = midpoint(ok, ng);
        (check(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <typename T>
enable_if_t<is_floating_point_v<T>, T>
bin_search(T ok, T ng, function<bool(T)> check)
{
    // midpointが成立するように浮動小数型を整数型にbit_castするクラス
    class OrderedBitcastFloat
    {
    public:
        using UInt = conditional_t<sizeof(T) == 4, uint32_t, conditional_t<sizeof(T) == 8, uint64_t, void>>;
        static_assert(!is_same_v<UInt, void>, "T must be float(4), double(8)");

        T real;       // 元の実数
        UInt int_key; // マッピング整数

        OrderedBitcastFloat(T x) : real(x), int_key(real_to_int_key(x)) {}
        OrderedBitcastFloat(UInt u) : real(int_key_to_real(u)), int_key(u) {}

    private:
        static constexpr UInt msb()
        {
            return UInt(1) << (8 * sizeof(UInt) - 1);
        }

        // 実数 → マッピング整数
        static UInt real_to_int_key(T x)
        {
            UInt bits = bit_cast<UInt>(x);
            if (bits & msb())
            {
                // 符号ビット＝1（負数領域）：反転
                return ~bits;
            }
            else
            {
                // 符号ビット＝0（正数領域）：MSB bit を足してオフセット
                return bits | msb();
            }
        }

        // マッピング整数 → 実数
        static T int_key_to_real(UInt u)
        {
            UInt bits;
            if (u & msb())
            {
                // MSB=1 → 正数領域：MSBを落とす
                bits = u & ~msb();
            }
            else
            {
                // MSB=0 → 負数領域：反転を戻す
                bits = ~u;
            }
            return bit_cast<T>(bits);
        }
    };

    OrderedBitcastFloat temp_ok(ok), temp_ng(ng);

    while (max(temp_ok.int_key, temp_ng.int_key) - min(temp_ok.int_key, temp_ng.int_key) > 1)
    {
        OrderedBitcastFloat mid(midpoint(temp_ok.int_key, temp_ng.int_key));
        (check(mid.real) ? temp_ok : temp_ng) = mid;
    }

    return temp_ok.real;
}

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

template <typename T>
enable_if_t<is_integral_v<T>, T>
bin_search(T ok, T ng, function<bool(T)> check)
{
    while (max(ok, ng) - min(ok, ng) > 1)
    {
        T mid = midpoint(ok, ng);
        (check(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <typename T>
enable_if_t<is_floating_point_v<T>, T>
bin_search(T ok, T ng, function<bool(T)> check)
{
    // midpointが成立するように浮動小数型を整数型にbit_castするクラス
    class OrderedBitcastFloat
    {
    public:
        using UInt = conditional_t<sizeof(T) == 4, uint32_t, conditional_t<sizeof(T) == 8, uint64_t, void>>;
        static_assert(!is_same_v<UInt, void>, "T must be float(4), double(8)");

        T real;       // 元の実数
        UInt int_key; // マッピング整数

        OrderedBitcastFloat(T x) : real(x), int_key(real_to_int_key(x)) {}
        OrderedBitcastFloat(UInt u) : real(int_key_to_real(u)), int_key(u) {}

    private:
        static constexpr UInt msb()
        {
            return UInt(1) << (8 * sizeof(UInt) - 1);
        }

        // 実数 → マッピング整数
        static UInt real_to_int_key(T x)
        {
            UInt bits = bit_cast<UInt>(x);
            if (bits & msb())
            {
                // 符号ビット＝1（負数領域）：反転
                return ~bits;
            }
            else
            {
                // 符号ビット＝0（正数領域）：MSB bit を足してオフセット
                return bits | msb();
            }
        }

        // マッピング整数 → 実数
        static T int_key_to_real(UInt u)
        {
            UInt bits;
            if (u & msb())
            {
                // MSB=1 → 正数領域：MSBを落とす
                bits = u & ~msb();
            }
            else
            {
                // MSB=0 → 負数領域：反転を戻す
                bits = ~u;
            }
            return bit_cast<T>(bits);
        }
    };

    OrderedBitcastFloat temp_ok(ok), temp_ng(ng);

    while (max(temp_ok.int_key, temp_ng.int_key) - min(temp_ok.int_key, temp_ng.int_key) > 1)
    {
        OrderedBitcastFloat mid(midpoint(temp_ok.int_key, temp_ng.int_key));
        (check(mid.real) ? temp_ok : temp_ng) = mid;
    }

    return temp_ok.real;
}

Back to top page