Smallest Element that is larger than target

Given a sorted array, find the smallest element larger than target

sample array:

sssssssssssssss eeeeeeeeeeeeeee Bbbbbbbbbbbbbbbb

Three cases for mid:

1. mid = target, search right for last target element

2. mid < target, search right

3. mid > target, search left, including mid

Moving rule:

Left side pinches when on target or smaller than target

Right side pinches when larger than target

End condition:

two elements left in array, both >= target

Post Processing:

check left > target, then right > target, return -1

public int smallerLargerThan(int[] array){
    if (array.length == 0) return -1;
    int left = 0;
    int right = array.length - 1;
    
    while( left < right - 1){ //prevent inf loop: {target, output}
        int mid = left + (right - left) / 2; 
        if (mid == target){
            left = mid;
        } else if (mid < target){
            left = mid;
        } else {
            right = mid;
        }
    }        
    if (array[left] > target) return left;
    if (array[right] > target) return right;
    return -1;
}
    

TC: O(logN) reduce by half each time

SC: O(1) no additional data structs used