Modified Binary Search

ceilSearch.cpp

int ceilSearch(int arr[], int low, int high, int x) 
{ 
    if(x <= arr[low]) return low;  
    if(x > arr[high]) return -1;   
    int mid = low + (high - low)/2;
    
    if(arr[mid] == x) 
        return mid; 
            
    /* If x is greater than arr[mid], then either arr[mid + 1] 
        is ceiling of x or ceiling lies in arr[mid+1...high] */  
    else if(arr[mid] < x) 
    { 
        if(mid + 1 <= high && x <= arr[mid+1]) 
            return mid + 1; 
        else 
            return ceilSearch(arr, mid+1, high, x); 
    } 
    
    /* If x is smaller than arr[mid], then either arr[mid]  
         is ceiling of x or ceiling lies in arr[low...mid-1] */    
    else
    { 
        if(mid - 1 >= low && x > arr[mid-1]) 
            return mid; 
        else     
            return ceilSearch(arr, low, mid - 1, x); 
    } 
}