Binary search
(include/search/binary_search.hpp)

• View this file on GitHub
• Last update: 2021-11-12 22:57:03+09:00
• Include: #include "include/search/binary_search.hpp"

二分探索をする関数が定義されています。

---

binary_search(ok, ng, f, diff)

引数

• ok - f(ok) が真となる十分大きい(または十分小さい)値
• ng - f(ng) が偽となる十分小さい(または十分大きい)値
• f - f(x) というコードで呼び出せて、bool 型の値を返すもの(関数への参照, operator() が定義されているクラスのオブジェクト 等)
• diff - 整数値の二分探索では $1$、実数値の二分探索では許容誤差 ($10^{-9}$ など)

戻り値

ok と ng の間の値で、f(x) が真となるギリギリの値

より厳密に言うと ok と ng の中間の値 mid で f(mid) を呼び出し、結果が真なら ok = mid と、偽なら ng = mid とすることを繰り返して探索範囲を狭めていき、ok と ng の差が diff 以下になった時の ok の値を返します。

---

Verified with

• test/search/binary_search/1.test.cpp
• test/search/binary_search/2.test.cpp
• test/search/binary_search/3.test.cpp

Code

//! @file binary_search.hpp

#ifndef CP_LIBRARY_BINARY_SEARCH_HPP
#define CP_LIBRARY_BINARY_SEARCH_HPP

#include <cassert>
#include <type_traits>
#include <utility>

#ifndef CP_LIBRARY_ASSERT
//! @brief Assert macro
#  define CP_LIBRARY_ASSERT(...) assert(__VA_ARGS__)
#  define CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

namespace lib {

//! @brief Find the minimum or maximum value that satisfies the condition.
//! @tparam Tp Return type (deduced from parameters)
//! @tparam Func callable type (function reference, class with operator(), ...)
//! @param ok Initial value for which the condition is satisfied
//! @param ng Initial value for which the condition is not satisfied
//! @param f Callable object that takes 1 parameter of Tp and returns bool indicating if the condition is satisfied
//! @param diff Difference (end condition of binary search). 1 for integers, small value (e.g. 1e-9) for real numbers
//! @return minimum value (if ok < ng) or maximum value (if ok > ng)
//! @note One and only one boundary value between ok and ng must exist.
//! @note Time complexity: O(log(|ok - ng|))
template <typename Tp, typename Func>
[[nodiscard]] Tp binary_search(Tp ok, Tp ng, const Func& f, const Tp diff = 1) {
  static_assert(std::is_same_v<decltype(std::declval<Func>()(std::declval<Tp>())), bool>);
  CP_LIBRARY_ASSERT(f(ok));
  CP_LIBRARY_ASSERT(!f(ng));

  if (ok < ng)
    while (ng - ok > diff) {
      const Tp mid       = ok + (ng - ok) / 2;
      (f(mid) ? ok : ng) = mid;
    }
  else
    while (ok - ng > diff) {
      const Tp mid       = ng + (ok - ng) / 2;
      (f(mid) ? ok : ng) = mid;
    }

  return ok;
}

}  // namespace lib

#ifdef CP_LIBRARY_ASSERT_NOT_DEFINED
#  undef CP_LIBRARY_ASSERT
#  undef CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

#endif  // CP_LIBRARY_BINARY_SEARCH_HPP

#line 1 "include/search/binary_search.hpp"

//! @file binary_search.hpp

#ifndef CP_LIBRARY_BINARY_SEARCH_HPP
#define CP_LIBRARY_BINARY_SEARCH_HPP

#include <cassert>
#include <type_traits>
#include <utility>

#ifndef CP_LIBRARY_ASSERT
//! @brief Assert macro
#  define CP_LIBRARY_ASSERT(...) assert(__VA_ARGS__)
#  define CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

namespace lib {

//! @brief Find the minimum or maximum value that satisfies the condition.
//! @tparam Tp Return type (deduced from parameters)
//! @tparam Func callable type (function reference, class with operator(), ...)
//! @param ok Initial value for which the condition is satisfied
//! @param ng Initial value for which the condition is not satisfied
//! @param f Callable object that takes 1 parameter of Tp and returns bool indicating if the condition is satisfied
//! @param diff Difference (end condition of binary search). 1 for integers, small value (e.g. 1e-9) for real numbers
//! @return minimum value (if ok < ng) or maximum value (if ok > ng)
//! @note One and only one boundary value between ok and ng must exist.
//! @note Time complexity: O(log(|ok - ng|))
template <typename Tp, typename Func>
[[nodiscard]] Tp binary_search(Tp ok, Tp ng, const Func& f, const Tp diff = 1) {
  static_assert(std::is_same_v<decltype(std::declval<Func>()(std::declval<Tp>())), bool>);
  CP_LIBRARY_ASSERT(f(ok));
  CP_LIBRARY_ASSERT(!f(ng));

  if (ok < ng)
    while (ng - ok > diff) {
      const Tp mid       = ok + (ng - ok) / 2;
      (f(mid) ? ok : ng) = mid;
    }
  else
    while (ok - ng > diff) {
      const Tp mid       = ng + (ok - ng) / 2;
      (f(mid) ? ok : ng) = mid;
    }

  return ok;
}

}  // namespace lib

#ifdef CP_LIBRARY_ASSERT_NOT_DEFINED
#  undef CP_LIBRARY_ASSERT
#  undef CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

#endif  // CP_LIBRARY_BINARY_SEARCH_HPP

Back to top page