二分探索
(Src/Utility/BinarySearch.hpp)

View this file on GitHub
Last update: 2023-09-24 02:48:01+09:00
Include: #include "Src/Utility/BinarySearch.hpp"

概要

整数や実数を一つ引数にとり、真理値を返り値とする関数 $f$ を考えます。 $f$ に以下の性質の一方を満たすと仮定します。

ある値 $m$ が存在して、 $m$ 以下の値 $x$ では $f(x) = \text{true}$ 、 $m$ より大きい値 $x$ では $f(x) = \text{false}$
ある値 $m$ が存在して、 $m$ 未満の値 $x$ では $f(x) = \text{false}$ 、 $m$ 以上の値 $x$ では $f(x) = \text{true}$

このような場合で、 $m$ を発見して返します。

ライブラリの使い方

(1) 
template<class T, class Function>
T BinarySearch(T ok, T ng, const Function& f)

(2)
template<class T, class Function>
T BinarySearch(T ok, T ng, const Functioni& f, u32 upperLimit)

テンプレート引数

T

fの引数の型です。

制約:

(1) 整数型であること

(2) 算術型であること

(2) は浮動小数点数型等も許される。

Function

fの型です。

制約:

T型の値を一つ引数にとり、bool値を返り値とする関数オブジェクトであること
副作用が無いこと(特にエラーを吐きませんが、 $m$ を正しく発見できる保証が無いです)

引数

ok

制約: f(ok) = trueを満たすこと

ng

制約: f(ng) = falseを満たすこと

f

制約: 概要の条件を満たすこと

upperLimit

探索回数の上限を設定します。

返り値

$m$ を返します。

計算量の見積もり

(1) fを $\mid \text{ok} - \text{ng}\mid$ 回呼び出します。

(2) fをupperLimit回呼び出します。

アルゴリズム

名前の通り、二分探索しています。

所謂、めぐる式二分探索を採用しています。

(https://twitter.com/meguru_comp/status/697008509376835584)

メモ

2023/9/24: (1)においてunsignedな整数型も利用できるように修正しました。オーバーフローする問題を解消しました。

Depends on

標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

Verified with

Code

#pragma once

#include "../Template/TypeAlias.hpp"

#include <cmath>
#include <functional>
#include <type_traits>
#include <utility>

namespace zawa {

namespace internal {

template <class T>
T MidPoint(T a, T b) {
    if (a > b) std::swap(a, b);
    return a + ((b - a) >> 1);
}

template <class T>
T Abs(T a, T b) {
    return (a >= b ? a - b : b - a);
}

} // namespace zawa::internal

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f) {
    static_assert(std::is_integral_v<T>, "T must be integral type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    while (internal::Abs(ok, ng) > 1) {
        T mid{ internal::MidPoint(ok, ng) };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f, u32 upperLimit) {
    static_assert(std::is_signed_v<T>, "T must be signed arithmetic type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    for (u32 _{} ; _ < upperLimit ; _++) {
        T mid{ (ok + ng) / (T)2 };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

} // namespace zawa

#line 2 "Src/Utility/BinarySearch.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Utility/BinarySearch.hpp"

#include <cmath>
#include <functional>
#include <type_traits>
#include <utility>

namespace zawa {

namespace internal {

template <class T>
T MidPoint(T a, T b) {
    if (a > b) std::swap(a, b);
    return a + ((b - a) >> 1);
}

template <class T>
T Abs(T a, T b) {
    return (a >= b ? a - b : b - a);
}

} // namespace zawa::internal

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f) {
    static_assert(std::is_integral_v<T>, "T must be integral type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    while (internal::Abs(ok, ng) > 1) {
        T mid{ internal::MidPoint(ok, ng) };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f, u32 upperLimit) {
    static_assert(std::is_signed_v<T>, "T must be signed arithmetic type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    for (u32 _{} ; _ < upperLimit ; _++) {
        T mid{ (ok + ng) / (T)2 };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

} // namespace zawa

二分探索 (Src/Utility/BinarySearch.hpp)

概要