Ceil_in_a_Sorted_Array.java

/*

Given a sorted array arr[] and an integer x, find the index (0-based) of the smallest element in arr[] that is greater than or equal to x. This element is called the ceil of x. If such an element does not exist, return -1.

Note: In case of multiple occurrences of ceil of x, return the index of the first occurrence.

Examples

Input: arr[] = [1, 2, 8, 10, 11, 12, 19], x = 5
Output: 2
Explanation: Smallest number greater than 5 is 8, whose index is 2.
Input: arr[] = [1, 2, 8, 10, 11, 12, 19], x = 20
Output: -1
Explanation: No element greater than 20 is found. So output is -1.
Input: arr[] = [1, 1, 2, 8, 10, 11, 12, 19], x = 0
Output: 0
Explanation: Smallest number greater than 0 is 1, whose indices are 0 and 1. The index of the first occurrence is 0.
Constraints:
1 ≤ arr.size() ≤ 106
1 ≤ arr[i] ≤ 106
0 ≤ x ≤ arr[n-1]

*/
class Solution {
    public int findCeil(int[] arr, int x) {
        // code here
        int low = 0;
        int high = arr.length-1;
        int res = -1;
        while(low <=high){
            int guess = (low+high)/2;
            if(x>arr[guess]){
                low = guess +1;
            }
            else{
                res = guess ;
                high = guess-1;
            }
        }
        return res;
        
    }
}