binary-search.hpp File Reference

Go to the source code of this file.

Description

Textbook implementation of the classical binary search over continuous domain.

The domain is given by its lower and upper end points. Within this domain, a breaking point is located, where the result of a probe predicate flips from false to true. For the core search, the invariant is assumed, implying that the predicate(lower) ≡ false and predicate(upper) ≡ true.

For good convergence, it is advisable to enter the search with rather tight bounds. For the case that it's not clear if the invariant holds for both ends, two alternative entrance points are provided, which check the condition on the interval ends and possibly shift and expand the search domain in case the assumption is broken.

See also

stress-test-rig.hpp

SchedulerStress_test

Definition in file binary-search.hpp.

#include "lib/meta/function.hpp"
#include <utility>

Functions
template<class FUN , typename PAR >
auto	binarySearch (FUN &&fun, PAR lower, PAR upper, PAR epsilon)
template<class FUN , typename PAR >
auto	binarySearch_inner (FUN &&fun, PAR lower, PAR upper, PAR epsilon)
	binary search: actual search loop More...
template<class FUN , typename PAR >
auto	binarySearch_upper (FUN &&fun, PAR lower, PAR upper, PAR epsilon)
	entrance point to binary search to ensure the upper point indeed fulfils the test. More...

Namespaces
	lib
	Implementation namespace for support and library code.