基于函数而不是集合的二进制搜索或迭代器？

Question

举个简单的例子，假设我想使用二分查找求 N 的平方根。但是我不想自己实现二进制搜索，而是使用 std::lower_bound 或类似的。我可以写类似

的东西吗

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);
}

是否有这样的函数，而不是从集合的迭代器中获取值，而是从回调函数中获取值？

或者，有没有一种方法可以基于函数而不是集合创建迭代器，这样我就可以做类似的事情：

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

我知道我可以自己编写这个函数或迭代器。我在问标准库中是否存在这样的功能，因为它看起来很有用，但我找不到它。

Answer 1

C++20 的标准库包括范围，基本上就是为这类东西而生的。你需要 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
}

这将创建序列 0, 1, 2, ..., x (iota(0, x + 1))，对每个元素 (| transform(square)) 求平方（将 | 读作 "pipe," a la sh)，搜索第一个大于或等于被基数的，并给出其 index/original 值（通过将其位置与序列的 begin 进行差分）。对于非负积分 x、0 <= sqrt(x) <= x，因此 iota(0, x + 1) 是一个合适的来源。在 square 中插入 std::cerr << x << "\n"; 确认 std::lower_bound 不会退回到线性搜索。

Godbolt

基于函数而不是集合的二进制搜索或迭代器？

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

c++

binary-search

lower-bound