如何用std::lower_bound实现满足谓词的最小k值二分查找？

你的场景刚好符合STL中分界点查找的典型需求：存在一个最小的k，使得is_possible_in_less_than_k_steps(args, k)从false转为true，且之后始终为true（谓词单调非递减）。以下是两种基于STL的实现方式：

方式1：用C++17的std::partition_point（推荐） #

std::partition_point专门用于在已分区的序列中查找第一个不满足谓词的元素，完美匹配你的场景。我们只需要用一个简单的整数迭代器模拟[min, max]的区间，再传入对应的谓词即可：

首先定义一个轻量的整数迭代器（如果用C++20可以直接用std::views::iota替代，无需手动实现迭代器）：

#include <algorithm>
#include <iterator>

struct IntIterator {
    using value_type = unsigned;
    using difference_type = std::ptrdiff_t;
    using pointer = const unsigned*;
    using reference = const unsigned&;
    using iterator_category = std::forward_iterator_tag;

    unsigned current;
    explicit IntIterator(unsigned c) : current(c) {}
    unsigned operator*() const { return current; }
    IntIterator& operator++() { ++current; return *this; }
    bool operator!=(const IntIterator& other) const { return current != other.current; }
};

然后替换自定义二分逻辑：

unsigned find_min_k(unsigned min, unsigned max, const Args& args) {
    auto begin = IntIterator(min);
    auto end = IntIterator(max + 1); // 区间为[min, max]，end设为max+1确保覆盖所有值
    
    // 谓词：返回!is_possible(...)，即分界点前的元素都满足该谓词
    auto it = std::partition_point(begin, end, [&](unsigned k) {
        return !is_possible_in_less_than_k_steps(args, k);
    });
    
    return *it;
}

方式2：用std::lower_bound #

std::lower_bound原本用于查找第一个不小于目标值的元素，但通过自定义比较函数，也可以适配你的场景：

unsigned find_min_k(unsigned min, unsigned max, const Args& args) {
    auto begin = IntIterator(min);
    auto end = IntIterator(max + 1);
    
    // 比较函数：当is_possible(k)为false时，k应在"true"的左侧
    auto it = std::lower_bound(begin, end, true, [&](unsigned k, bool) {
        return !is_possible_in_less_than_k_steps(args, k);
    });
    
    return *it;
}

注意事项 #

• 两种实现的逻辑和你原代码完全一致，时间复杂度都是O(log(max-min))
• 如果使用C++20，无需手动实现IntIterator，可以用std::views::iota(min, max+1)生成区间，代码会更简洁：

  #include <ranges>
  
  auto range = std::views::iota(min, max + 1);
  auto it = std::partition_point(range.begin(), range.end(), [&](unsigned k) {
      return !is_possible_in_less_than_k_steps(args, k);
  });
  return *it;
  

• 若max是unsigned类型的最大值，max+1会溢出，此时需要特殊处理边界（和你原代码的边界情况一致）

内容的提问来源于stack exchange，提问作者Sergey Mirzoev