Find elements in a vector which lie within specified ranges

Question

I have a vector of integer elements in sorted. An example is given below:

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

Now given the following "start" and "end" ranges I want to find out which elements of vector A fall into the start and end ranges.

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

For example,

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}

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

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

If the vector is sorted, as you have shown it to be, you can use binary search to locate the index of the element that is higher than the lower value of the range and index of element that is lower than the higher value of the range.

That will make your search O(log(N)).

You can use std::lower_bound and std::upper_bound, which requires the container to be partially ordered, which is true in your case.

If the vector is not sorted, linear iteration is the best you can do.