我正在尝试为二分搜索方法创建自定义比较函数
lower_bound()
。我尝试阅读文档并搜索,但我无法弄清楚 comp
函数的参数应该如何排序。
首先,在常规二元参数
comp
中,哪一个是val
(目标值),哪一个是向量中的项?
其次,我怎样才能包含更多的论点?
我有一个
vector<int>
。
我希望我的comp
做的是获取val
,减去向量项,如果结果大于整数y
,则返回true(这不能作为全局变量来完成,因为它经常变化)。
我还想要另一个类似的
comp
来检查结果是否小于x
。
我怎样才能构建这样的比较器?
请告诉我是否需要更多说明。我正在寻找的是如何构建比较器的解释。如果这样的教程(有非常清晰的解释)已经存在,请指出我,因为我的搜索没有产生任何有用的东西。
TIA。
编辑:同样,我已经阅读了文档。我不明白他们如何构建
comp
,所以请停止重复文档所说的内容。如果可以的话,请详细解释一下这个概念。我的问题不是缺乏搜索,而是缺乏理解搜索时发现的内容。
我希望我的 comp 做的是获取 val,减去向量项,如果结果大于整数则返回 true
y
std::lower_bound
及其参数comp
的要求是向量按相同的comp
顺序排序。这意味着 comp
必须对订单进行编码。
从技术上讲,您的
comp
正是这样做的。它将整数分为两组:“大于 y”和“不大于 y”。换句话说,y 等于 y-1,y+1 等于y+2。这就是你所说的std::lower_bound
。
如果你的向量是这样排序的,那么就不存在未定义的行为。
std::lower_bound
将返回一个迭代器到向量的正确一半。对于 val<=y
,它将是迭代器进入较小的一半,对于 val>y
,它将在另一半中。
但这可能不是您想要的。您似乎正在努力解决的心理问题是,您尝试根据您认为应该返回的内容(返回
comp
)来定义 (x-val)<y
,而不是考虑向量顺序以及要查找的元素。
老实说,你的描述太模糊了,我什至不知道你想找到哪个元素。鉴于
{1, 5, 9, 23}
和 y=6
,我不知道你想要哪个元素。