c++ - 查找 vector 中位于指定范围内的元素

Question

我有一个排序的整数元素 vector 。示例如下:

vector<int> A ={3,4,5,9,20,71,89,92,100,103,109,110,121,172,189,194,198};

现在给定以下“开始”和“结束”范围，我想找出 vector A 的哪些元素落入开始和结束范围。

int startA=4; int endA=8;
int startB=20; int endB=99;
int startA=120; int endC=195;

例如，

elements lying in range startA and startB are: {4,5}
elements lying in range startA and startB are: {20,71,89,92}
elements lying in range startC and startC are: {121,172,189,194}

执行此操作的一种方法是遍历“A”的所有元素并检查它们是否位于指定范围内。有没有其他更有效的方法来找出 vector 中满足给定范围的元素

Answer 1

One way to do this is to iterate over all elements of "A" and check whether they lie between the specified ranges. Is there some other more efficient way to find out the elements in the vector satisfying a given range

如果 vector 已排序，如您所示，您可以使用二进制搜索来定位高于范围较低值的元素的索引和低于较高值的元素的索引的范围。

这将使您的搜索复杂度为 O(log(N))。

您可以使用 std::lower_bound和 std::upper_bound ，这需要对容器进行部分排序，这在您的情况下是正确的。

如果 vector 没有排序，线性迭代是你能做的最好的。