在向量中查找位于指定范围内的元素

Question

我有一个整数元素的矢量排序.下面给出一个例子:

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

现在给出以下"开始"和"结束"范围,我想找出向量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"的所有元素并检查它们是否位于指定范围之间.是否有其他更有效的方法来找出满足给定范围的向量中的元素

Answer 1

一种方法是迭代"A"的所有元素并检查它们是否位于指定范围之间.是否有其他更有效的方法来找出满足给定范围的向量中的元素

如果对矢量进行了排序,正如您所示,您可以使用二进制搜索来定位元素的索引,该索引高于范围的较低值,并且元素的索引低于范围的较高值.

这将使你的搜索O(log(N)).

您可以使用std::lower_bound和std::upper_bound,这需要部分订购容器,这在您的情况下是正确的.

如果矢量未排序,则线性迭代是您可以做的最好的.

Answer 2

如果向量被排序,您需要做的就是使用专用函数来查找起始范围迭代器和结束范围迭代器 - std::lower_bound和std::upper_bound.例如.:

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
   std::vector<int> A ={3,4,5,9,20,71,89,92,100,103,109,110,121,172,189,194,198};
   auto start = std::lower_bound(A.begin(), A.end(), 4);
   auto end = std::upper_bound(A.begin(), A.end(), 8);
   for (auto it = start; it != end; it++) {
      std::cout << *it << " ";
   }
   std::cout << std::endl;
}

//or the C++1z version (works in VS2015u3)
int main() {
   std::vector<int> A ={3,4,5,9,20,71,89,92,100,103,109,110,121,172,189,194,198};
   std::copy(std::lower_bound(A.begin(), A.end(), 4),
             std::upper_bound(A.begin(), A.end(), 8),
             std::ostream_iterator<int>(cout, " "));
   std::cout << std::endl;
}

然而,只有在startX <= endX您运行任意数字之前,您可能希望测试适当的条件时才会起作用...

使用std::lower_bound和搜索绑定迭代器std::upper_bound会花费成本O(log(N))但是必须说明在平均情况下迭代元素范围是O(N),并且范围可能包含向量中的所有元素...