Library
This documentation is automatically generated by online-judge-tools/verification-helper
Binary Search
(src/opt/binary_search.hpp)
- View this file on GitHub
- Last update: 2020-12-08 15:39:54+09:00
- Include:
#include "src/opt/binary_search.hpp"
Required by
Exponential Search
(src/opt/exponential_search.hpp)
Verified with
- test/aizu-online-judge/0323.test.cpp
- test/aizu-online-judge/1342.test.cpp
- test/aizu-online-judge/ALDS1_14_C.test.cpp
- test/library-checker/zalgorithm_2.test.cpp
Code
#pragma once
/*
* @file binary_search.hpp
* @brief Binary Search
*/
#include <cassert>
#include <limits>
#include <tuple>
#include <vector>
namespace workspace {
/*
* @fn binary_search
* @brief binary search on a discrete range.
* @param ok pred(ok) is true
* @param ng pred(ng) is false
* @param pred the predicate
* @return the closest point to (ng) where pred is true
*/
template <class Iter, class Pred>
typename std::enable_if<
std::is_convertible<decltype(std::declval<Pred>()(std::declval<Iter>())),
bool>::value,
Iter>::type
binary_search(Iter ok, Iter ng, Pred pred) {
assert(ok != ng);
typename std::make_signed<decltype(ng - ok)>::type dist(ng - ok);
while (1 < dist || dist < -1) {
const Iter mid(ok + dist / 2);
if (pred(mid))
ok = mid, dist -= dist / 2;
else
ng = mid, dist /= 2;
}
return ok;
}
/*
* @fn binary_search
* @brief binary search on the real number line.
* @param ok pred(ok) is true
* @param ng pred(ng) is false
* @param eps the error tolerance
* @param pred the predicate
* @return the boundary point
*/
template <class Real, class Pred>
typename std::enable_if<
std::is_convertible<decltype(std::declval<Pred>()(std::declval<Real>())),
bool>::value,
Real>::type
binary_search(Real ok, Real ng, const Real eps, Pred pred) {
assert(ok != ng);
for (auto loops = 0; loops != std::numeric_limits<Real>::digits &&
(ok + eps < ng || ng + eps < ok);
++loops) {
const Real mid{(ok + ng) / 2};
(pred(mid) ? ok : ng) = mid;
}
return ok;
}
/*
* @fn parallel_binary_search
* @brief parallel binary search on discrete ranges.
* @param ends a vector of pairs; pred(first) is true, pred(second) is false
* @param pred the predicate
* @return the closest points to (second) where pred is true
*/
template <class Array,
class Iter = typename std::decay<
decltype(std::get<0>(std::declval<Array>()[0]))>::type,
class Pred>
typename std::enable_if<
std::is_convertible<
decltype(std::declval<Pred>()(std::declval<std::vector<Iter>>())[0]),
bool>::value,
std::vector<Iter>>::type
parallel_binary_search(Array ends, Pred pred) {
std::vector<Iter> mids(std::size(ends));
for (;;) {
bool all_found = true;
for (size_t i{}; i != std::size(ends); ++i) {
const Iter &ok = std::get<0>(ends[i]);
const Iter &ng = std::get<1>(ends[i]);
const Iter mid(
ok + typename std::make_signed<decltype(ng - ok)>::type(ng - ok) / 2);
if (mids[i] != mid) {
all_found = false;
mids[i] = mid;
}
}
if (all_found) break;
const auto res = pred(mids);
for (size_t i{}; i != std::size(ends); ++i) {
(res[i] ? std::get<0>(ends[i]) : std::get<1>(ends[i])) = mids[i];
}
}
return mids;
}
/*
* @fn parallel_binary_search
* @brief parallel binary search on the real number line.
* @param ends a vector of pairs; pred(first) is true, pred(second) is false
* @param eps the error tolerance
* @param pred the predicate
* @return the boundary points
*/
template <class Array,
class Real = typename std::decay<
decltype(std::get<0>(std::declval<Array>()[0]))>::type,
class Pred>
typename std::enable_if<
std::is_convertible<
decltype(std::declval<Pred>()(std::declval<std::vector<Real>>())[0]),
bool>::value,
std::vector<Real>>::type
parallel_binary_search(Array ends, const Real eps, Pred pred) {
std::vector<Real> mids(std::size(ends));
for (auto loops = 0; loops != std::numeric_limits<Real>::digits; ++loops) {
bool all_found = true;
for (size_t i{}; i != std::size(ends); ++i) {
const Real ok = std::get<0>(ends[i]);
const Real ng = std::get<1>(ends[i]);
if (ok + eps < ng || ng + eps < ok) {
all_found = false;
mids[i] = (ok + ng) / 2;
}
}
if (all_found) break;
const auto res = pred(mids);
for (size_t i{}; i != std::size(ends); ++i) {
(res[i] ? std::get<0>(ends[i]) : std::get<1>(ends[i])) = mids[i];
}
}
return mids;
}
} // namespace workspace#line 2 "src/opt/binary_search.hpp"
/*
* @file binary_search.hpp
* @brief Binary Search
*/
#include <cassert>
#include <limits>
#include <tuple>
#include <vector>
namespace workspace {
/*
* @fn binary_search
* @brief binary search on a discrete range.
* @param ok pred(ok) is true
* @param ng pred(ng) is false
* @param pred the predicate
* @return the closest point to (ng) where pred is true
*/
template <class Iter, class Pred>
typename std::enable_if<
std::is_convertible<decltype(std::declval<Pred>()(std::declval<Iter>())),
bool>::value,
Iter>::type
binary_search(Iter ok, Iter ng, Pred pred) {
assert(ok != ng);
typename std::make_signed<decltype(ng - ok)>::type dist(ng - ok);
while (1 < dist || dist < -1) {
const Iter mid(ok + dist / 2);
if (pred(mid))
ok = mid, dist -= dist / 2;
else
ng = mid, dist /= 2;
}
return ok;
}
/*
* @fn binary_search
* @brief binary search on the real number line.
* @param ok pred(ok) is true
* @param ng pred(ng) is false
* @param eps the error tolerance
* @param pred the predicate
* @return the boundary point
*/
template <class Real, class Pred>
typename std::enable_if<
std::is_convertible<decltype(std::declval<Pred>()(std::declval<Real>())),
bool>::value,
Real>::type
binary_search(Real ok, Real ng, const Real eps, Pred pred) {
assert(ok != ng);
for (auto loops = 0; loops != std::numeric_limits<Real>::digits &&
(ok + eps < ng || ng + eps < ok);
++loops) {
const Real mid{(ok + ng) / 2};
(pred(mid) ? ok : ng) = mid;
}
return ok;
}
/*
* @fn parallel_binary_search
* @brief parallel binary search on discrete ranges.
* @param ends a vector of pairs; pred(first) is true, pred(second) is false
* @param pred the predicate
* @return the closest points to (second) where pred is true
*/
template <class Array,
class Iter = typename std::decay<
decltype(std::get<0>(std::declval<Array>()[0]))>::type,
class Pred>
typename std::enable_if<
std::is_convertible<
decltype(std::declval<Pred>()(std::declval<std::vector<Iter>>())[0]),
bool>::value,
std::vector<Iter>>::type
parallel_binary_search(Array ends, Pred pred) {
std::vector<Iter> mids(std::size(ends));
for (;;) {
bool all_found = true;
for (size_t i{}; i != std::size(ends); ++i) {
const Iter &ok = std::get<0>(ends[i]);
const Iter &ng = std::get<1>(ends[i]);
const Iter mid(
ok + typename std::make_signed<decltype(ng - ok)>::type(ng - ok) / 2);
if (mids[i] != mid) {
all_found = false;
mids[i] = mid;
}
}
if (all_found) break;
const auto res = pred(mids);
for (size_t i{}; i != std::size(ends); ++i) {
(res[i] ? std::get<0>(ends[i]) : std::get<1>(ends[i])) = mids[i];
}
}
return mids;
}
/*
* @fn parallel_binary_search
* @brief parallel binary search on the real number line.
* @param ends a vector of pairs; pred(first) is true, pred(second) is false
* @param eps the error tolerance
* @param pred the predicate
* @return the boundary points
*/
template <class Array,
class Real = typename std::decay<
decltype(std::get<0>(std::declval<Array>()[0]))>::type,
class Pred>
typename std::enable_if<
std::is_convertible<
decltype(std::declval<Pred>()(std::declval<std::vector<Real>>())[0]),
bool>::value,
std::vector<Real>>::type
parallel_binary_search(Array ends, const Real eps, Pred pred) {
std::vector<Real> mids(std::size(ends));
for (auto loops = 0; loops != std::numeric_limits<Real>::digits; ++loops) {
bool all_found = true;
for (size_t i{}; i != std::size(ends); ++i) {
const Real ok = std::get<0>(ends[i]);
const Real ng = std::get<1>(ends[i]);
if (ok + eps < ng || ng + eps < ok) {
all_found = false;
mids[i] = (ok + ng) / 2;
}
}
if (all_found) break;
const auto res = pred(mids);
for (size_t i{}; i != std::size(ends); ++i) {
(res[i] ? std::get<0>(ends[i]) : std::get<1>(ends[i])) = mids[i];
}
}
return mids;
}
} // namespace workspace