Help me write a binary search for boundary values (extracting sub lists)
-
06-07-2019 - |
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!
Solution
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);
}
OTHER TIPS
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.
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.