src/Helper/BinarySearch.hpp

• View this file on GitHub
• Last update: 2020-04-28 01:08:47+09:00
• Include: #include "src/Helper/BinarySearch.hpp"

概要

整数の範囲についての二分探索。計算量はO(log |ok - ng|)。

Verified with

• test/aoj/0646.test.cpp

Code

/// @docs src/Helper/BinarySearch.md
template <class F> long long binary_search(long long ok, long long ng, F check) {
    while (std::abs(ok - ng) > 1) {
        long long mid = (ok + ng) / 2;
        (check(mid) ? ok : ng) = mid;
    }
    return ok;
}

#line 1 "src/Helper/BinarySearch.hpp"
/// @docs src/Helper/BinarySearch.md
template <class F> long long binary_search(long long ok, long long ng, F check) {
    while (std::abs(ok - ng) > 1) {
        long long mid = (ok + ng) / 2;
        (check(mid) ? ok : ng) = mid;
    }
    return ok;
}

Back to top page