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

Question

I have an array of sorted vectors,

vector< int> 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 :

        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.

Answer 1

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:

  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

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.

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.

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.

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

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.