Upper Bound, thesarfo

Same idea as lower bound, but for the first index i where arr[i] > x (strictly greater, not greater-or-equal).

public static int upperBound(int[] arr, int n, int x){
    int low = 0, high = n - 1;
    int ans = n;

    while(low <= high){
        int mid = (low + high) / 2;

        if(arr[mid] > x){
            ans = mid;
            high = mid - 1;
        } else{
            low = mid + 1;
        }
    }
    return ans;
}

Criterion	Lower Bound	Upper Bound
Condition	`arr[i] >= x`	`arr[i] > x`
Search left when	`arr[mid] >= x`	`arr[mid] > x`
Final answer	smallest `i` with `arr[i] >= x`	smallest `i` with `arr[i] > x`