使用 std::lower_bound 作为谓词中的第一个 true

Question

假设我们的目标是在我们发明的算法实现范围内最大限度地减少执行某些操作所需的步骤数量

is_possible_in_less_than_k_steps(args, int k);

很明显，returns 有一个划分点，在该划分点之前，returns 为 0，在该划分点之后，returns 为 1。

有没有办法使用STL算法对解进行bin search？

尝试重新发明轮子，但这对我来说看起来不太好。

unsigned l = min, r = max;
while (l < r)
{
    unsigned m = (l + r) >> 1;
    bool possible = is_it_possible(helis, pads_tree, m);
    if (!possible)
    {
        l = m + 1;
    }
    else
    {
        r = m;
    }
}
return l;

Answer 1

对于 C++20 范围，这是相当微不足道的：

auto range = std::ranges::views::iota(min, max);
auto partition_point = std::ranges::partition_point(
    range,
    [&](unsigned i) { return !is_it_possible(helis, pads_tree, i); }
);
if (partition_point == std::ranges::end(range)) {
    // no partition point found
} else {
    // *partition_point is the value you're looking for
}

演示