代码之家 › 专栏 › 技术社区 › SHUBHAM KUMAR

这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

lower-bound binary-search algorithm c++

SHUBHAM KUMAR · 技术社区 · 2 年前

如果我有2个向量,一个按升序排列,另一个按降序排列:

vector<int> inc{1,2,3,4,6,7}, dec{7,6,4,3,2,1};

以下两个表达式是否总是给出相同的结果?或者,它们的工作方式有什么不同吗?

lower_bound(inc.rbegin(), inc.rend(), some_number, greater<int>()) // #1

lower_bound(dec.begin(), dec.end(), some_number, greater<int>()) // #2

我觉得它们是一样的,但在最近一次关于Codeforce的比赛中,一个被接受了,另一个没有。

1 回复 | 直到 2 年前

Ted Lyngmo 2 年前

根据算法, std::lower_bounds 的视角下,除了迭代器类型(一个是反向迭代器,另一个不是)之外没有其他区别,但它并不关心这一点。

在这两种情况下,它都将执行相同的算法步骤,并返回一个迭代器,该迭代器指向在这两个情况下都携带相同值的元素,或者 end() / rend() 迭代器。

一个微小的差异可能是速度。我预计使用反向迭代器的版本会慢一点,但我还没有测量。

因此,除了返回的迭代器类型不同,可能一个比另一个慢之外,您将从两个版本中获得相同的值。

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

1 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

2 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

2 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

2 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

2 年前