旋转数组最小值

将一个非递减序列的某一处切一刀，再把前半段序列放到后半段序列的后面，这样组成的新序列叫做“旋转数组”。要求获取一个旋转数组的最小值。给定数组arr及它的大小n，请返回最小值。

测试样例：
[4,1,2,3,3],5
返回：1

思路

如果旋转的长度为0,即arr[0]<arr[n-1],数组仍然是一个非递减序列,直接返回第一个元素即可.

否则将数组看成两个排序的子数组, 最小的元素就是两个数组的分界点.用二分查找的思想去查找分界点.

如果arr[lo]>arr[mid],说明arr[mid]肯定落在了第二个子数组上,此时hi=mid.
如果arr[mid]>arr[hi],说明arr[mid]肯定落在了第一个子数组上,此时lo=mid.
lo和hi逐步向分界点逼近,直到arr[lo]是第一个子数组的最后一个元素,arr[hi]元素是第二个子数组的第一个元素,即分界点.此时返回arr[hi].

如果上述两个条件都不满足,说明arr[lo]<=arr[mid],并且arr[hi]>=arr[mid],又有arr[lo]>=arr[hi],得出arr[lo]=arr[mid]=arr[hi].此时没有办法缩小范围.只能通过遍历的方式去查找最小值.

代码

 public int getMin(int[] arr, int n) {
        int lo=0,hi=n-1;
        int mid=0;
        if(arr[lo]<arr[hi]){
            return arr[lo];
        } 
        while(lo!=hi-1){                 
            mid=lo+(hi-lo)/2;            
            if(arr[lo]>arr[mid]){    
                hi=mid;
            }
            else if(arr[mid]>arr[hi]){ 
                lo=mid;
            }
            else{              
                while(lo<=hi&&arr[lo]==arr[hi]){
                    lo++;
                }
                return arr[lo];
            }
        }
        return arr[hi];
    }