c++ - 如何在 C++ 中实现对函数的二分查找？

Question

我在 C++ 中遇到了一个代价高昂的子问题:将近一分钟。此外，这个子问题-- bool f(x) --变长为x范围从 [1,n]。

在[1,n]的范围内，有一个点1<j<n, f(j) = true这样 f(k), k < j是总是假的...和f(m), j < m 始终为真。

我需要找到那个点。

---

我需要做的是从x=1 开始的二分搜索 (这样它甚至不会触及 x 接近 n 的耗时区域)。

---

现在，我正在手动执行二进制搜索实现，我从函数的最小值开始(因此，f(1)，这是错误的)。然后我将输入值加倍，直到达到 f(x) is happy 的状态(真的)。这部分没什么大不了的。我可以手动完成。

接下来，我想在 [x/2,x] 范围内对 first 值进行二分搜索，其中 f(x) = true (注意 f(x/2) 必须等于 false，因为 f(1) = false ...我需要在不犯任何错误的情况下完成它。而且这是事情变得有点毛茸茸的地方。

---

所以我怀疑 C++ 已经实现了这个，但我是 C++ 的新手，并且对库的经验有限。我目前正在查看二进制搜索，但我没有看到一种方法可以对函数的所有值从 false 变为 true 的实际点进行 bin 搜索。

相反，它似乎是贪婪的:它只会捕获第一个 true它发现，而不是最小值 true .

我如何在 C++ 中执行此操作？

---

我的搜索功能的输入如下:

std::vector<int> range(max);
for (int j = 0; j < max; j++){
    range[j] = j;
}

std::some_search_function(range.begin(),range.end(),f(int value))

哪里f(...)是之前的 bool 函数...

并且它需要具有我所描述的属性:从它正在搜索的项目中的第一个值开始，并返回最早的项目，其中 f(...)很满意...

Answer 1

您可以实现一个自定义迭代器，根据它表示的索引“指向”真或假，并使用 std::lower_bound查找第一个 true 值的函数。