Binary search to find the range in which the number lies
Why not to use standard library functions?
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
for (int input = 10; input < 55; input++) {
cout << input << ": ";
// Your desire:
vector<int> v = { 12, 20, 32, 40, 52 };
if (input < v.front() || input > v.back()) {
cout << "Not found" << endl;
} else {
auto it = upper_bound(v.begin(), v.end(), input);
cout << it - v.begin() - 1 << endl;
}
}
}
Note: a pretty-cool site - http://en.cppreference.com/w/cpp/algorithm
This will work under the condition that min(A[i]) <= key <=max(A[i])
int binary_search(int A[],int key,int left, int right)
{
while (left <= right) {
int middle = left + (right - left) / 2;
if (A[middle] < key)
left = middle+1;
else if(A[middle] > key)
right = middle-1;
else
return middle;
}
return (left - 1);
}
A range in C or C++ is normally given as the pointing directly to the lower bound, but one past the upper bound. Unless you're feeling extremely masochistic, you probably want to stick to that convention in your search as well.
Assuming you're going to follow that, your last = midpoint-1;
is incorrect. Rather, you want to set last to one past the end of the range you're going to actually use, so it should be last = midpoint;
You also only really need one comparison, not two. In a binary search as long as the two bounds aren't equal, you're going to set either the lower or the upper bound to the center point, so you only need to do one comparison to decide which.
At least by convention, in C++, you do all your comparisons using <
instead of <=
, >
, etc. Any of the above can work, but following the convention of using only <
keeps from imposing extra (unnecessary) requirements on contained types.
Though most interviewers probably don't care, there's also a potential overflow when you do midpoint = (left + right)/2;
. I'd generally prefer midpoint = left + (right - left)/2;
Taking those into account, code might look something like this:
template <class T>
T *lower_bound(T *left, T *right, T val) {
while (left < right) {
T *middle = left + (right - left) / 2;
if (*middle < val)
left = middle + 1;
else
right = middle;
}
return left;
}
template <class T>
T *upper_bound(T *left, T *right, T val) {
while (left < right) {
T *middle = left + (right - left) / 2;
if (val < *middle)
right = middle;
else
left = middle + 1;
}
return left;
}