Searching for a range [x,y] in a sorted vector in C++ [using lower_bound() and upper_bound() ]

时间:2022-09-28 18:21:17

I have an array of sorted vectors,

我有一个排序的矢量数组,

vector< int> b[1000009];

vector b [1000009];

Now I have to search the range between x and y inclusive in the row b[factor].
'factor', 'x' and 'y' are all integers.
I have used the following approch :

现在我必须在行b [因子]中搜索x和y之间的范围。 'factor','x'和'y'都是整数。我使用了以下approch:

        int lb,ub;
        if(b[factor][0]>=x){lb=0;}
        else
            {
                lb=upper_bound(b[factor].begin(),b[factor].end(),x)-b[factor].begin();
                while(b[factor][lb-1]>=x)lb--;
            }
        if(b[factor][sz2-1]<=y)
            {
                ub=sz2-1;
            }
        else {
                ub=lower_bound(b[factor].begin(),b[factor].end(),y)-b[factor].begin();
                while(b[factor][ub]>y)ub--;
            }

But this approach ain't giving correct answers all the time. And besides I would like to used some comparator functions to achieve the same. This is my first time with lower_bound() and upper_bound(). So please tell me how to implement the comparator function here.

但这种方法并没有给出正确的答案。此外,我想使用一些比较器功能来实现相同的功能。这是我第一次使用lower_bound()和upper_bound()。那么请告诉我如何在这里实现比较器功能。

1 个解决方案

#1


3  

std::lower_bound returns the position of the first element whose value is greater than or equal to the argument. std::upper_bound returns the position of the first element that is greater than the argument. You can use these to iterate over the range of values between x and y like this:

std :: lower_bound返回其值大于或等于参数的第一个元素的位置。 std :: upper_bound返回大于参数的第一个元素的位置。您可以使用它们迭代x和y之间的值范围,如下所示:

  auto vb = b[factor].begin();
  auto ve = b[factor].end();
  auto lb = lower_bound(vb,ve,x);
  auto ub = upper_bound(vb,ve,y);
  for (auto i=lb; i!=ub; ++i) {
    // Do something with *i
  }

Let's take this example. Say our vector contains these values:

我们来看看这个例子吧。假设我们的向量包含以下值:

1 3 4 7 9

1 3 4 7 9

And let's say x=3 and y=7. std::lower_bound(vb,ve,x) will return the position of the first value that is greater than or equal to 3. Since there is a value that is equal to 3, its position is what we will get for the lower bound.

让我们说x = 3和y = 7。 std :: lower_bound(vb,ve,x)将返回大于或等于3的第一个值的位置。由于有一个等于3的值,它的位置是我们将得到的下限。

std::upper_bound(vb,be,y) will return the position of the first value that is greater than 7. That would be the position of 9 in this case.

std :: upper_bound(vb,be,y)将返回大于7的第一个值的位置。在这种情况下,这将是9的位置。

So our loop is going from the position of 3 up to, but not including, the position of 9, which is exactly the range of values that we want.

所以我们的循环从3的位置开始,但不包括9的位置,这正是我们想要的值的范围。

Now what if x=5 and y=6. There would be no values in that range. What would it do?

现在如果x = 5和y = 6怎么办?该范围内没有值。它会做什么?

The first value that is greater than or equal to 5 is 7. The first value that is greater than 6 is also 7. So lb and ub would be the same position! Our loop would terminate immediately, which is exactly what we want since there are no elements in our range.

大于或等于5的第一个值是7.第一个大于6的值也是7.所以lb和​​ub将是相同的位置!我们的循环会立即终止,这正是我们想要的,因为我们的范围内没有元素。

#1


3  

std::lower_bound returns the position of the first element whose value is greater than or equal to the argument. std::upper_bound returns the position of the first element that is greater than the argument. You can use these to iterate over the range of values between x and y like this:

std :: lower_bound返回其值大于或等于参数的第一个元素的位置。 std :: upper_bound返回大于参数的第一个元素的位置。您可以使用它们迭代x和y之间的值范围,如下所示:

  auto vb = b[factor].begin();
  auto ve = b[factor].end();
  auto lb = lower_bound(vb,ve,x);
  auto ub = upper_bound(vb,ve,y);
  for (auto i=lb; i!=ub; ++i) {
    // Do something with *i
  }

Let's take this example. Say our vector contains these values:

我们来看看这个例子吧。假设我们的向量包含以下值:

1 3 4 7 9

1 3 4 7 9

And let's say x=3 and y=7. std::lower_bound(vb,ve,x) will return the position of the first value that is greater than or equal to 3. Since there is a value that is equal to 3, its position is what we will get for the lower bound.

让我们说x = 3和y = 7。 std :: lower_bound(vb,ve,x)将返回大于或等于3的第一个值的位置。由于有一个等于3的值,它的位置是我们将得到的下限。

std::upper_bound(vb,be,y) will return the position of the first value that is greater than 7. That would be the position of 9 in this case.

std :: upper_bound(vb,be,y)将返回大于7的第一个值的位置。在这种情况下,这将是9的位置。

So our loop is going from the position of 3 up to, but not including, the position of 9, which is exactly the range of values that we want.

所以我们的循环从3的位置开始,但不包括9的位置,这正是我们想要的值的范围。

Now what if x=5 and y=6. There would be no values in that range. What would it do?

现在如果x = 5和y = 6怎么办?该范围内没有值。它会做什么?

The first value that is greater than or equal to 5 is 7. The first value that is greater than 6 is also 7. So lb and ub would be the same position! Our loop would terminate immediately, which is exactly what we want since there are no elements in our range.

大于或等于5的第一个值是7.第一个大于6的值也是7.所以lb和​​ub将是相同的位置!我们的循环会立即终止,这正是我们想要的,因为我们的范围内没有元素。