Binary search or iterator based on a function instead of a collection?

Question

As a simple example, let's say I want to find the square root of N by using binary search. But I don't want to implement the binary search myself, but use std::lower_bound or similar. Can I write something like

int square(int x) {
  return x * x;
}

int square_root(int N) {
  // Assume I know the results is between 0 and 10000.
  return std::lower_bound(0, 10000, square, N);
}

Is there a function like that that instead of taking values from the iterators of a collection takes the values from a callback function?

Or, is there a way to create iterators based on a function rather than a collection so that I can do something like:

return std::lower_bound(func_it(0, square), func_it(10000, square), N);

I know I can write this function or iterator myself. I'm asking if such functionality exists in the standard library because it seems like it would be useful but I wasn't able to find it.

Answer 1

C++20's standard library includes ranges, which was basically made for this kind of stuff. You'll want a transform_view:

int square(int x) { return x * x; }
int sqrt(int x) {
    auto space = std::views::iota(0, x + 1) | std::views::transform(square);
    return std::lower_bound(space.begin(), space.end(), x) - space.begin();
}
int main() {
    std::cout << "sqrt(123): " << sqrt(123) << "\n"; // gives 12: (12-1)^2 < 123 <= 12^2
}

This creates the sequence 0, 1, 2, ..., x (iota(0, x + 1)), squares every element (| transform(square)) (read that | as the "pipe," a la sh), searches for the first one greater than or equal to the radicand, and gives its index/original value (by differencing its location with the sequence's begin). For nonnegative integral x, 0 <= sqrt(x) <= x, so iota(0, x + 1) is a suitable source. Inserting a std::cerr << x << "\n"; in square confirms that std::lower_bound does not fall back to linear search.

Godbolt