將一個非遞減序列的某一處切一刀卦睹，再把前半段序列放到后半段序列的后面泳猬，這樣組成的新序列叫做“旋轉(zhuǎn)數(shù)組”括勺。要求獲取一個旋轉(zhuǎn)數(shù)組的最小值均澳。給定數(shù)組arr及它的大小n，請返回最小值垃杖。
測試樣例：
[4,1,2,3,3],5
返回：1
思路
如果旋轉(zhuǎn)的長度為0,即arr[0]<arr[n-1],數(shù)組仍然是一個非遞減序列,直接返回第一個元素即可.
否則將數(shù)組看成兩個排序的子數(shù)組, 最小的元素就是兩個數(shù)組的分界點.用二分查找的思想去查找分界點.
如果arr[lo]>arr[mid],說明arr[mid]肯定落在了第二個子數(shù)組上,此時hi=mid.
如果arr[mid]>arr[hi],說明arr[mid]肯定落在了第一個子數(shù)組上,此時lo=mid.
lo和hi逐步向分界點逼近,直到arr[lo]是第一個子數(shù)組的最后一個元素,arr[hi]元素是第二個子數(shù)組的第一個元素,即分界點.此時返回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];
}
