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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#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; } |
Can’t you do something simpler by using std::pair<unsigned, unsigned> for ranges, sort them, then use std::lower_bound() to search for make_pair(val, val)?