用于查找最接近键的双精度的二进制搜索模板

Question

C++ 中是否有模板，它允许在排序向量中找到最接近键的值，以及 returns 它的索引（迭代器）。我发现，returns 只有一个布尔值。

已编辑：这个问题的动机是二分搜索 returns 是一个布尔值。我得出结论，在返回布尔值时，迭代器也是已知的。返回它，我可以找出 找到了哪个 元素。没有提供这种二分查找的原因是什么？

Answer 1

我不知道你是否想避免对你的容器/数组进行排序，所以我将采用 post 最通用的方式。答案是——不。如果你不想对容器进行排序，没有现成的模板，但你可以简单地编写自己的函数，如下所示：

template<typename iterator_t, typename value_t, typename comparator_t>
iterator_t nearest_element(iterator_t begin, iterator_t end, value_t value, comparator_t comparator) {
    return std::min_element(begin, end, [value, &comparator](double lhs, double rhs) {
        return comparator(std::abs(lhs - value), std::abs(rhs - value));
    });
}

template<typename iterator_t, typename value_t>
iterator_t nearest_element(iterator_t begin, iterator_t end, value_t value) {
    return nearest_element(begin, end, value, std::less<value_t>());
}

这只是简单的数学运算，最近的元素是从搜索值中减去它的绝对值最小的元素。上面的代码仍然允许您更改比较器（但隐藏减法/std::fabs），因此它也可用于查找最远的值。

用法（没有指定的比较器）很简单，就像任何其他标准函数一样：

std::vector<double> vec {2., 5., -4.};
auto it = nearest_element(vec.begin(), vec.end(), -10.);
std::cout << *it << std::endl;

用于查找最接近键的双精度的二进制搜索模板

Binary search template for finding a double nearest to the key

c++

templates

binary-search