把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾椎工，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素发钝。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)菇篡，該數(shù)組的最小值為1漩符。 NOTE：給出的所有元素都大于0，若數(shù)組大小為0驱还，請返回0嗜暴。
一個(gè)有序數(shù)組旋轉(zhuǎn)后，分成了兩個(gè)有序的子數(shù)組议蟆，這樣一個(gè)大數(shù)組相當(dāng)于一定程度上是有序的闷沥。因此可以嘗試使用二分法。mid = low + (high - low)/2咐容，始終將mid和high處的值作比較舆逃。分三種情況。
- array[mid] > array[high] 此時(shí)mid肯定還處于左側(cè)數(shù)組之中，要找的最小值在右側(cè)數(shù)組中路狮，最小值肯定在mid的右側(cè)虫啥，所以可以直接把low移動(dòng)到mid的下一個(gè)位置，即low=mid+1奄妨。
- array[mid] < array[high] 此時(shí)mid肯定處于右側(cè)數(shù)組之中涂籽，要找的最小值可能為mid的值或者mid右邊的值，所以high只能縮小到mid砸抛，不能縮小到mid-1评雌。
- array[mid] == array[high]，此時(shí)無法分辨mid處于左半數(shù)組還是右半數(shù)組直焙。比如{1, 0, 1, 1, 1}和{1, 1, 1, 0, 1}都是數(shù)組{0, 1, 1, 1, 1}的旋轉(zhuǎn)數(shù)組景东。此時(shí)mid處和high處的值一樣，若根據(jù)low縮小范圍奔誓，對于{1, 0, 1, 1, 1}最小值將被跳過斤吐；如果根據(jù)high縮小范圍，對于{1, 1, 1, 0, 1}最小值也會(huì)被跳過丝里。所以此時(shí)只能放棄二分查找曲初，既然mid處和high處的值相同，那么就讓high--杯聚，讓mid和high前面的值作比較臼婆。如果mid和high都是最小值，就算放棄了high也能在mid處找到最小值幌绍。
只要low<high（不含等于）颁褂，就一直重復(fù)以上比較過程，一直比到low與high指向同一個(gè)元素傀广，到low==high的時(shí)候退出颁独，其實(shí)low == high時(shí)候還進(jìn)入循環(huán)，也沒有錯(cuò)伪冰，此時(shí)只會(huì)造成high--誓酒，而我們返回的是array[low]，值不會(huì)影響贮聂，但是何必進(jìn)行這次無意義的比較呢靠柑。
PS：為什么要把mid和high作比較，而不能讓mid和low作比較吓懈，試想如果最后范圍縮小到剩下{1, 2}此時(shí)array[low] == array[mid]歼冰，如果low++就跳過最小元素了，此種情況可以寫一個(gè)min(int low, int high)方法耻警，直接返回[low, high]范圍內(nèi)的最小值隔嫡。比起用high來和mid比較甸怕，麻煩了不少。
public int minNumberInRotateArray(int [] array) {
if (array==null || array.length == 0) {
return 0;
}
int low = 0;
int high = array.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
// 此時(shí)mid一定在左半數(shù)組中腮恩，最小值在mid的右邊
if (array[mid] > array[high]) {
low = mid + 1;
// 此時(shí)mid一定在右半數(shù)組中梢杭，最小值在mid的左邊或就是mid本身
} else if (array[mid] < array[high]) {
high = mid;
// 暫時(shí)放棄二分查找，和前一個(gè)字符繼續(xù)比較
} else {
high--;
}
}
// low == high時(shí)推出循環(huán)并返回
return array[low];
}
