There is a binary search algorithm for a monotonic function. Is it possible to implement it on standard embedded tools from C ++ (STL)?

For example, I found a binary array search, it is implemented and implemented well. However, not a word about real binary search.

The approximate algorithm itself, which is being discussed:

#define EPS 1E-9 double f(double x) { ///some monotonically increasing function on [a, b], for example f(x) = x^3: return x*x*x; } double binarySearch(double C, double a, double b) { double low = a, high = b; double mid; while(abs(low-high) > EPS) { mid = low + (high - low) / 2; if f(mid) < C low = mid; else high = mid; } return mid; }
  • "we are talking about finding the argument of a function in which it takes the desired value" - and how do you propose to consider the situation when the value lies in the desired interval, but the function never accepts it? - VTT
  • @VTT Looks like continuous monotonic functions. - HolyBlackCat 7:58 pm
  • @HolyBlackCat Yes. But even if the function is continuous and monotonous, this does not mean that it will take all values ​​on the interval due to errors in floating-point calculations. This is not a mathematical spherical function in a vacuum. - VTT
  • @VTT Therefore, as I know, in such cases there is no comparison of F(m) == need , but a comparison of need - F(m) < EPS . - witaway pm
  • @VTT And as I know, very often, in order to avoid looping or too long working time, the algorithm uses not while , but for with a hard number of iterations. - witaway

2 answers 2

This is possible, but not all ready-made tools are present in the standard C ++ library.

  1. Standard iterators provide discrete access. Therefore, we need some way to discretize the domain of the function while preserving the possibility of random access. For example, to use arithmetic with fixed accuracy - at least with the accuracy that is required in your task.

  2. We need a random access iterator over "virtual" sequences, i.e. based on the results of a function call generated on the fly, and not on physical values ​​in the memory. Such iterators or something similar, as far as I know, are present in Boost, but not in the current standard C ++ library. (What is strange, because the concept is very natural and in demand.)

  3. The concept of strict equality does not work very well (to put it mildly) with floating arithmetic, so for binary search you will have to use boundary algorithms: std::lower_bound , std::upper_bound , std::equal_range ...

Here is an example of such an iterator written “on the knee” (it may well be that some operations are “redundant”, that is, the algorithms used will not be in demand, but I did not ask myself this question, but immediately implemented “more”)

 #include <cstdint> #include <iterator> template <typename F, typename ARG, std::uintmax_t PRECISION> struct FunctionIterator { using iterator_category = std::random_access_iterator_tag; using value_type = ARG; using difference_type = std::intmax_t; using pointer = ARG *; using reference = ARG; F f; std::intmax_t x; FunctionIterator(F f, ARG x) : f(std::move(f)), x((std::intmax_t) (x * PRECISION)) {} ARG arg() const { return (ARG) x / PRECISION; } ARG operator *() const { return f(arg()); } FunctionIterator &operator++() { ++x; return *this; } FunctionIterator &operator++(int) { FunctionIterator old = *this; ++*this; return old; } FunctionIterator &operator +=(std::intmax_t rhs) { x += rhs; return *this; } friend FunctionIterator operator +(const FunctionIterator &lhs, std::intmax_t rhs) { return FunctionIterator(lhs) += rhs; } FunctionIterator &operator--() { --x; return *this; } FunctionIterator &operator--(int) { FunctionIterator old = *this; --*this; return old; } FunctionIterator &operator -=(std::intmax_t rhs) { x -= rhs; return *this; } friend FunctionIterator operator -(const FunctionIterator &lhs, std::intmax_t rhs) { return FunctionIterator(lhs) -= rhs; } friend std::intmax_t operator -(const FunctionIterator &lhs, const FunctionIterator &rhs) { return lhs.x - rhs.x; } friend bool operator ==(const FunctionIterator &lhs, const FunctionIterator &rhs) { return lhs.x == rhs.x; } friend bool operator !=(const FunctionIterator &lhs, const FunctionIterator &rhs) { return lhs.x != rhs.x; } friend bool operator <(const FunctionIterator &lhs, const FunctionIterator &rhs) { return lhs.x < rhs.x; } };

Having obtained such an iterator, we will be able to transfer it to standard algorithms, including to perform a search.

An example of using it to perform a binary search on a segment, say [-100, 100] with an accuracy of 0.001

 #include <algorithm> #include <iostream> double f(double x) { return x * x * x; } int main() { FunctionIterator<double (*)(double), double, 1000> a(f, -100), b(f, 100), c = std::lower_bound(a, b, 5.0); std::cout << c.arg() << " " << *c << std::endl; }

Conclusion

 1.71 5.00021

Increasing the multiplier to 100000 we get

 1.70998 5.00004

And so on, trying to monitor the danger of overflow std::intmax_t .

  • Yes, it is necessary to try to write such a perversion ... Probably, it was only at the time of XT, when in games the sine tables were considered in advance and in the form of fractions - as two integers. - Mikhailo

No, there is no such thing in the standard library.

But, frankly, your algorithm is somewhat, um, surprising. Then it makes sense to do a binary search for the solution f(x) == 0 . Well, for generalization ... I sketched on my knee here :)

 template< typename Double, typename Func, typename = std::enable_if_t<std::is_floating_point<Double>::value> > Double binEq(Double left, Double right, Double eps, Func f) { using std::swap; Double x = left; if (left > right) swap(left,right); Double fl = f(left), fr = f(right); if (fl*fr > 0) throw std::exception("Wrong range"); while ( right - left > eps ) { x = (left + right)/Double(2.0); if (fl * f(x) < 0) right = x; else left = x; } return x; }
  • one
    Because of std::exception does not compile. You need std::runtime_error or something like that instead. - HolyBlackCat
  • @HolyBlackCat In VC ++ compiles, I sculpted under it ... There can be any processing - just a message that the solution is not guaranteed, so we will not try :( - Harry
  • one
    The studio is in its repertoire. :) std::exception should not have a constructor with a string parameter. (Minus is not mine.) - HolyBlackCat pm