Help me write a binary search for boundary values (extracting sub lists)

Question

Let's say I have an array of lots of values (C++ syntax, sorry):

vector<double> x(100000);

This array is sorted such that x[n] > x[n-1].

I would like a function to retrieve an array of all values in the range [a, b] (that's inclusive). Some interface like:

void subarray(const double a, const double b, vector<double> &sub) {
    ...
}

When this function completes, sub will contain the n values that fell in the range [a, b].

Of course a linear search is easy:

void subarray(const double a, const double b, vector<double> &sub) {
    for (size_t i = 0; i < data.size(); i++) {
        if (a <= data[i] && data[i] <= b) {
            sub.push_back(data[i]);
        }
    }
}

However, because data is sorted, I should be able to do this much faster using a binary search. Who wants to take a stab at it? Any language is permitted!

Answer 1

You already appear to know that a binary search can be used to find the range, and implementations of those are easily found.

Everything else is just getting trivial array manipulation.

Answer 2

What you're asking is a bit confusing regarding the the exact range properties and the types. However, you can tweak the following C++ code to suit your needs. The basic intuition is to use lower_bound and upper_bound to find the positions in the array that delineate the range you're looking for.

void subarray(const double a, const double b, vector <double> &sub, vector <int> pn) {
    vector <int>::const_iterator begin, end;
    begin = lower_bound(pn.begin(), pn.end(), a);
    end = upper_bound(pn.begin(), pn.end(), b);
    sub.insert(sub.begin(), begin, end);
}

Answer 3

The easy solution:

• use binary search to find the lowest a and the highest b
• allocate a new array
• copy the values

Code is trivial as said before.