the key is to locate the range which satisfy if x<y then array[x] < array[y].
then we can decide if the element is within [x,y] or outside of [x,y], narrowing down the search space by roughly half.
If there is duplicate (array[middle] == array[right], then we can’t decide whether to throw away [x,y] entirely or jump into [x,y]. A solution is to only remove array[right] (right -=1)
Search for a range