algorithm - Check if a number exists in a given set of ranges -

algorithm - Check if a number exists in a given set of ranges -

suppose have set of n ranges, (a1, b1) (a2, b2) (a3, b3) ... (an, bn), ai denotes starting point , bi denotes ending point of range. (ai, bi positive integers)

how check using binary search if given integer, x, exists in @ to the lowest degree 1 of n ranges?

my approach:

sort ranges x-coordinate first , y-coordinate.

find smallest x-coordinate greater or equal x.

check if range satisfied.

if yes, have solution.

now, if range doesnt contain x, should next step?

or, should solution exclusively different?

what got problem description have pairs (a1,b1) , (a2,b2). ax start of range , bx end. given number n , want search if number in of ranges. first sort merge overlapping ranges , apply binary search:

#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { vector < pair <int , int> > b; b.push_back(make_pair(5,10)); b.push_back(make_pair(75,100)); b.push_back(make_pair(33,67)); b.push_back(make_pair(9,21)); b.push_back(make_pair(28,67)); int m = b.size(); sort(b.begin(), b.end()); int j = 0; (int = 1; < m; i++) { if (b[i].first <= b[j].second) { if (b[i].second > b[j].second) { b[j].second = b[i].second; } } else { j++; b[j] = b[i]; } } m = j + 1; for(int = 0; i< m;i ++) { cout << b[i].first << " " << b[i].second << endl; } // apply binary search homecoming 0; }

i hope solve problem. have left binary search part exercise.

algorithm sorting binary-search