Kyopro Library
 
読み取り中…
検索中…
一致する文字列を見つけられません
binary_search.hpp ファイル

[ソースコード]

関数

template<typename T, typename Judge>
BinarySearch (T ok, T ng, Judge judge)
 二分探索
 
template<typename T, typename Judge>
BinarySearchIteration (T ok, T ng, Judge judge, int iter=100)
 回数指定二分探索
 
template<typename T, typename Judge>
bool CheckMonotonicity (T start, T step, ll iter, Judge judge)
 単調性の確認
 

関数詳解

◆ BinarySearch()

template<typename T, typename Judge>
T BinarySearch ( T ok,
T ng,
Judge judge )

二分探索

条件 judge を満たす ok と ng の境界を二分探索によって求める。

覚え書き
O(log(|ok - ng|) * f)

binary_search.hpp8 行目に定義があります。

◆ BinarySearchIteration()

template<typename T, typename Judge>
T BinarySearchIteration ( T ok,
T ng,
Judge judge,
int iter = 100 )

回数指定二分探索

条件 judge を満たす ok と ng の境界を二分探索によって求める。

覚え書き
O(iter * f)

binary_search.hpp21 行目に定義があります。

◆ CheckMonotonicity()

template<typename T, typename Judge>
bool CheckMonotonicity ( T start,
T step,
ll iter,
Judge judge )

単調性の確認

関数 judge が単調性を満たすか否かを確認する

引数
start開始要素
step探索幅
iter探索回数

binary_search.hpp36 行目に定義があります。