Range Search

Given an sorted array of integers, perform binary search to find the index of the range in which the number lies. A range is specified by index of its lower bound.

Example :

array 12 20 32 40 52

          ^   ^   ^   ^   ^

index  0   1   2   3   4

Given the number -> 19 (It lies between index 0 and 1), return 0
Given the number -> 22 (It lies between index 1 and 2), return 1
Given the number -> 40 (It lies between index 3 and 4), return 3

Solution
Use binary search.

Suppose we are at index i , then there are two possibilities:

A[i] < N , this implies that we need to check in (i+1, N)
• A[i] >= N   this implies that we need to check in (0, i)

Code

int range_search(int array[], int N, int begin, int end){

if(begin > end)

return -1;

     
int mid=(begin + end)/2;
     
if(array[mid] > N){

if(array[mid-1] <= N)

return mid-1;

else

return range_search(array, N, begin, mid-1);

}
else if(array[mid] <= N){

if(array[mid+1] > N)

return mid;

else

return range_search(array, N, mid+1, end);

} 

}

Complexity

• Time : O(log N)
• Space : O(1)