给定排序的矢量查找从负到正的过渡

Question

鉴于已排序std::vector<int>,我希望使用C++ 11-STD函数来查找元素从负变为正的索引.

我知道我可以使用二进制搜索来实现它,但我感兴趣的是标准库中是否有任何函数,类似于一元find_if,这将有助于此搜索(可能与正确的lambda表达式相关).

Answer 1

你应该找到lower_bound为0:

auto iter = std::lower_bound(vec.begin(), vec.end(), 0);

生成的迭代器将指向最早的位置,您可以在不中断元素排序的情况下插入0.同样,upper_bound将返回最右边的这样的迭代器.

算法的运行时间是 O(logN)