假设我有一个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
的索引。我在哪里弄糟?
[您在lower_bound
中使用的谓词与对vec
进行排序所使用的谓词不同。因此,您的代码段具有未定义的行为。
您仍然可以使用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。