C++中无需手写二分查找实现函数结果upper_bound的兼容方案

方案1：基于自定义整数迭代器+原生std::upper_bound（无需第三方库） #

既然你已经实现了随机访问的整数迭代器MyIntIt，完全可以跳过视图转换，直接把转换逻辑嵌入std::upper_bound的自定义比较器中，这样既不需要C++20 ranges，也能保证二分查找的O(log n)效率。

实现代码如下：

template <class ArgT,
          class ResultT,
          class TransformFunc,
          class Compare = std::less<ResultT>>
ArgT result_upper_bound(ResultT searched, ArgT begin, ArgT end, TransformFunc tf, Compare comp = Compare{}) {
    // 用自定义整数迭代器包装范围边界
    const auto first = MyIntIt<ArgT>(begin);
    const auto last = MyIntIt<ArgT>(end);

    // 调用std::upper_bound，在比较器中完成参数到结果的转换
    auto it = std::upper_bound(first, last, searched,
        [&tf, &comp](const ResultT& target, const ArgT& arg) {
            // 对应upper_bound的逻辑：返回target < tf(arg)（默认comp），即tf(arg) > target
            return comp(target, tf(arg));
        });

    // 解引用迭代器得到最终的参数值
    return *it;
}

这个方案的核心是利用std::upper_bound允许自定义比较器的特性，把原本需要视图做的转换逻辑放到比较步骤中，避免了对C++20 ranges的依赖，同时因为MyIntIt是随机访问迭代器，std::upper_bound会以最优的二分查找效率运行。

方案2：使用Boost.Counting Range（若Boost版本支持随机访问转换迭代器） #

如果你的Boost版本足够新（Boost 1.70+），boost::transform_iterator在底层迭代器是随机访问类型时，会自动继承随机访问迭代器的特性，此时可以结合boost::counting_range来实现：

#include <boost/range/counting_range.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/algorithm/range.hpp>

template <class ArgT,
          class ResultT,
          class TransformFunc,
          class Compare = std::less<ResultT>>
ArgT result_upper_bound(ResultT searched, ArgT begin, ArgT end, TransformFunc tf, Compare comp = Compare{}) {
    auto args_range = boost::counting_range(begin, end);
    auto transformed = args_range | boost::adaptors::transformed(tf);
    auto it = boost::algorithm::upper_bound(transformed, searched, comp);
    // 转换回原始参数值：迭代器距离起始的偏移量 + begin
    return begin + std::distance(args_range.begin(), it.base());
}

注意这里需要用it.base()获取转换迭代器的底层整数迭代器，再计算偏移得到原始参数值。如果你的Boost版本确实不支持随机访问的转换迭代器，这个方案会退化为线性查找，此时建议优先选方案1。

方案3：使用Abseil库的数值范围与转换视图 #

如果你可以引入Abseil库，absl::numeric_range提供了原生的整数随机访问范围，absl::MakeTransformView生成的视图同样保持随机访问特性，配合absl::upper_bound即可高效完成查找：

#include <absl/numeric/numeric_range.h>
#include <absl/algorithm/algorithm.h>
#include <absl/ranges/transform_view.h>

template <class ArgT,
          class ResultT,
          class TransformFunc,
          class Compare = std::less<ResultT>>
ArgT result_upper_bound(ResultT searched, ArgT begin, ArgT end, TransformFunc tf, Compare comp = Compare{}) {
    auto args_range = absl::numeric_range<ArgT>(begin, end);
    auto transformed = absl::MakeTransformView(args_range, tf);
    auto it = absl::upper_bound(transformed, searched, comp);
    return args_range.begin() + std::distance(transformed.begin(), it);
}

内容的提问来源于stack exchange，提问作者Георгий Гуминов