14#ifndef OR_TOOLS_ALGORITHMS_BINARY_SEARCH_H_
15#define OR_TOOLS_ALGORITHMS_BINARY_SEARCH_H_
22#include "absl/base/log_severity.h"
23#include "absl/functional/function_ref.h"
24#include "absl/log/check.h"
25#include "absl/numeric/int128.h"
26#include "absl/types/span.h"
79template <
class Po
int,
bool check_bounds = DEBUG_MODE>
80Point
BinarySearch(Point x_true, Point x_false, std::function<
bool(Point)> f);
115template <
class Po
int,
class Value>
116std::pair<Point, Value>
ConvexMinimum(absl::Span<const Point> sorted_points,
117 std::function<
Value(Point)> f);
123template <
class Po
int,
class Value>
125 std::pair<Point, Value> current_min,
126 absl::Span<const Point> sorted_points,
127 std::function<
Value(Point)> f);
130template <
class Po
int,
class Value>
132 absl::FunctionRef<
Value(Point)> f);
133template <
class Po
int,
class Value>
136 absl::FunctionRef<
Value(Point)> f);
149 return std::isnan(x);
153 return std::isnan(x);
157 return std::isnan(x);
162 if constexpr (std::is_same_v<T, absl::int128>) {
163 return (x < 0) == (y < 0);
164 }
else if constexpr (std::is_same_v<T, absl::uint128> ||
165 std::is_unsigned_v<T>) {
167 }
else if constexpr (std::is_signed_v<T>) {
168 return std::signbit(x) == std::signbit(y);
173template <
typename IntT>
175 if constexpr (std::is_integral_v<IntT>) {
176 if constexpr (std::is_unsigned_v<IntT>) {
179 return (IntT{-1} & IntT{3}) == IntT{3};
187template <
class Po
int>
195 midpoint = (x | y) - ((x ^ y) >> 1);
202 x < y ? x + (y - x) / 2
208 DCHECK_LE(midpoint, y) <<
"Overflow?";
209 DCHECK_GE(midpoint, x) <<
"Overflow?";
211 DCHECK_GE(midpoint, y) <<
"Overflow?";
212 DCHECK_LE(midpoint, x) <<
"Overflow?";
218template <
class Po
int,
bool check_bounds>
219Point
BinarySearch(Point x_true, Point x_false, std::function<
bool(Point)> f) {
220 if constexpr (check_bounds) {
221 CHECK(f(x_true)) << x_true;
222 CHECK(!f(x_false)) << x_false;
224 int num_iterations = 0;
225 constexpr int kMaxNumIterations = 1000000;
232 if (++num_iterations > kMaxNumIterations) {
234 <<
"The binary search seems to loop forever! This indicates that your"
235 " input types don't converge when repeatedly taking the midpoint";
246template <
class Po
int,
class Value>
248 absl::FunctionRef<Value(Point)> f) {
257 std::pair<Point, Value> current_min;
261 DCHECK_GT(mid,
begin);
262 const Value v = f(mid);
263 const Point before_mid = mid - 1;
264 const Value before_v = f(before_mid);
265 if (before_v == v)
return {before_mid, before_v};
268 current_min = {before_mid, before_v};
271 current_min = {mid, v};
275 if (
begin >=
end)
return current_min;
279template <
class Po
int,
class Value>
282 absl::FunctionRef<Value(Point)> f) {
285 DCHECK(current_min.first <
begin || current_min.first >=
end);
286 bool current_is_after_end = current_min.first >=
end;
288 const Value v = f(mid);
289 if (v >= current_min.second) {
292 if (current_is_after_end) {
300 DCHECK_GT(mid,
begin);
301 const Point before_mid = mid - 1;
302 const Value before_v = f(before_mid);
303 if (before_v == v)
return {before_mid, before_v};
305 current_min = {before_mid, before_v};
306 current_is_after_end =
true;
309 current_is_after_end =
false;
310 current_min = {mid, v};
317 const Value v = f(
begin);
318 if (v <= current_min.second)
return {
begin, v};
323template <
class Po
int,
class Value>
325 std::function<Value(Point)> f) {
326 auto index_f = [&](
int index) -> Value {
return f(sorted_points[index]); };
327 const auto& [index, v] =
329 return {sorted_points[index], v};
332template <
class Po
int,
class Value>
334 std::pair<Point, Value> current_min,
335 absl::Span<const Point> sorted_points,
336 std::function<Value(Point)> f) {
337 auto index_f = [&](
int index) -> Value {
return f(sorted_points[index]); };
338 std::pair<int, Value> index_current_min = std::make_pair(
339 is_to_the_right ? sorted_points.size() : -1, current_min.second);
341 index_current_min, 0, sorted_points.size(), index_f);
342 if (index == index_current_min.first)
return current_min;
343 return {sorted_points[index], v};
bool AreNumbersOfSameSign(const T &x, const T &y)
bool IsNanGeneric(const T &)
constexpr bool UsesTwosComplement()
std::function< int64_t(const Model &)> Value(IntegerVariable v)
This checks that the variable is fixed.
In SWIG mode, we don't want anything besides these top-level includes.
Point BinarySearchMidpoint(Point x, Point y)
ClosedInterval::Iterator end(ClosedInterval interval)
std::pair< Point, Value > RangeConvexMinimum(Point begin, Point end, absl::FunctionRef< Value(Point)> f)
Searches in the range [begin, end), where Point supports basic arithmetic.
Point BinarySearch(Point x_true, Point x_false, std::function< bool(Point)> f)
std::pair< Point, Value > ConvexMinimum(absl::Span< const Point > sorted_points, std::function< Value(Point)> f)
ClosedInterval::Iterator begin(ClosedInterval interval)