c++ - C++ lower_bound()搜索最接近目标值的元素

Question

假设我有一个vector，其元素是int类型。如何优雅地使用std::lower_bound()查找最接近目标值的元素？

我写了如下代码:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec {3,4,5,10};
    int target = 6;

    auto found {
        lower_bound(
            vec.begin(),
            vec.end(),
            target,
            [=] (int ele1, int ele2) {
                return (abs(ele1 - target) > abs(ele2 - target));
            }
        )
    };

    cout << (found-vec.begin()) << endl;

    return 0;
}

它返回 4的索引，即 found = vec.end()。相反，我想获取 2的索引。我在哪里弄糟？

Answer 1

您在lower_bound中使用的谓词与vec排序中使用的谓词不同。因此，您的代码段具有 undefined 的行为。

您仍然可以使用lower_bound来简单地查找target。

auto attempt = lower_bound(vec.begin(), vec.end(), target);

现在，您真正要查找的迭代器将是返回的迭代器，或者是下一个元素的迭代器:

auto found = attempt == vec.end() ? 
             vec.end() - 1 :   // last element is closest
             attempt == vec.begin() ? 
             vec.begin() :  // first element is closest
             abs(*attempt - target) < abs(*(attempt - 1) - target) ? 
             // somewhere in the middle, then the previous element could be closer
             attempt : attempt - 1;   

假设 vec是非空的，因此您可能还需要执行该检查。

这是 demo。