Utility/Bsearch.cpp

• View this file on GitHub
• Last update: 2021-03-24 15:18:21+09:00

Verified with

• test/Bsearch.test.cpp

Code

#pragma once
#include <optional>
#include <type_traits>
#include <cassert>

template <class T, class F, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
std::optional<T> Bsearch(T left, T right, F f) {
	if (left > right || !f(right)) {
		return std::nullopt;
	} else if (f(left)) {
		return left;
	}
	while (right - left > 1) {
		T middle = (left + right) / 2;
		(f(middle) ? right : left) = middle;
	}
	assert(!f(left));
	assert(f(right));
	return right;
}

#line 2 "Utility/Bsearch.cpp"
#include <optional>
#include <type_traits>
#include <cassert>

template <class T, class F, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
std::optional<T> Bsearch(T left, T right, F f) {
	if (left > right || !f(right)) {
		return std::nullopt;
	} else if (f(left)) {
		return left;
	}
	while (right - left > 1) {
		T middle = (left + right) / 2;
		(f(middle) ? right : left) = middle;
	}
	assert(!f(left));
	assert(f(right));
	return right;
}

Back to top page