Given a set of integer ranges defined as [LO, HI) and a value P, find which range P falls into.
My approach to this programming puzzle was to first define a range
as a struct
that can be sorted (thanks to operator <
), then perform binary search on a vector
of sorted ranges. The code is pretty self explanatory.
Example Input and Output
LO: 0, HI: 10
LO: 10, HI: 20
LO: 20, HI: 30
LO: 30, HI: 40
LO: 40, HI: 50
LO: 50, HI: 60
LO: 60, HI: 70
LO: 70, HI: 80
LO: 80, HI: 90
LO: 90, HI: 100
P = 15 falls in range LO: 10, HI: 20
P = 16 falls in range LO: 10, HI: 20
P = 4 falls in range LO: 0, HI: 10
P = 73 falls in range LO: 70, HI: 80
P = 25 falls in range LO: 20, HI: 30
P = 28 falls in range LO: 20, HI: 30
P = 19 falls in range LO: 10, HI: 20
P = 60 falls in range LO: 60, HI: 70
P = 83 falls in range LO: 80, HI: 90
P = 76 falls in range LO: 70, HI: 80
Program ended with exit code: 1
The Answer
#include <iostream>
#include <mutex>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
mutex cout_lock;
#define trace(x) { scoped_lock<mutex> lock(cout_lock); cout << x << endl; }
const int COUNT = 10;
struct range
{
unsigned int lo;
unsigned int hi;
bool in_range(unsigned int p) const { return lo <= p && p < hi; }
};
bool operator < (const range& lhs, const range& rhs)
{
return lhs.lo < rhs.lo;
}
ostream& operator << (ostream& os, const range& r)
{
os << "LO: " << r.lo << ", HI: " << r.hi;
return os;
}
range BinarySearch(const vector<range>& v, unsigned int p)
{
size_t index = v.size() / 2;
size_t step = index / 2 + 1;
while(true)
{
if(v[index].hi <= p) index += step;
if(v[index].lo > p) index -= step;
step /= 2;
if(step == 0) step = 1;
if(v[index].in_range(p)) break;
}
return v[index];
}
int main(int argc, char** argv)
{
srand((unsigned int)time(NULL));
vector<range> ranges =
{
{50, 60}, {60, 70}, {70, 80}, {80, 90}, {90, 100},
{0, 10}, {10, 20}, {20, 30}, {30, 40}, {40, 50}
};
sort(begin(ranges), end(ranges));
for(const auto& r : ranges)
trace(r);
for(int i = 0; i < COUNT; ++i)
{
unsigned int p = rand() % 100;
trace("P = " << p << " falls in range " << BinarySearch(ranges, p));
}
return 1;
}