Java日记2018-08-10

find minimum in rotated sorted array II
旋转数组找到最小值，其中数组有重复值

使用二分法，最右的值小于中间值，那么最小值在右边。left就应该mid+1的地方，否则最小的值在左边，right=mid
当有重复值，即相等的时候，直接left加1呗，或者right--

public static int findmin1(int[] arr){
        int left =0;
        int right = arr.length-1;
        
        while(left<right){
            int mid = (left+right)/2;
            System.out.println(mid);
            if(arr[right]<arr[mid]){
                left=mid+1;
            } else if(arr[right]>arr[mid]) {
                right=mid;
            } else{
                right--;
            }
        }
        System.out.println(arr[left]);
        return arr[left];
    }
    public static void main(String[] args){
        int[] arr={3,3,4,4,-1,1};
        findmin1(arr);
    }