将一个非递减序列的某一处切一刀，再把前半段序列放到后半段序列的后面，这样组成的新序列叫做“旋转数组”。要求获取一个旋转数组的最小值。给定数组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];
}
