Search an element in given N ranges | C ++ implementation of the approach ; Function to return the index of the range in which K lies and uses binary search ; Binary search ; Find the mid element ; If element is found ; Check in first half ; Check in second half ; Not found ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findNumber ( pair < int , int > a [ ] , int n , int K ) { int low = 0 , high = n - 1 ; while ( low <= high ) { int mid = ( low + high ) >> 1 ; if ( K >= a [ mid ] . first && K <= a [ mid ] . second ) return mid ; else if ( K < a [ mid ] . first ) high = mid - 1 ; else low = mid + 1 ; } return -1 ; } int main ( ) { pair < int , int > a [ ] = { { 1 , 3 } , { 4 , 7 } , { 8 , 11 } } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int k = 6 ; int index = findNumber ( a , n , k ) ; if ( index != -1 ) cout << index ; else cout << -1 ; return 0 ; }