聲明： 本總結(jié)僅為個(gè)人學(xué)習(xí)總結(jié)橙数，以防止遺忘而作尊流，不得轉(zhuǎn)載和商用。
問(wèn)題描述
假定一個(gè)排序數(shù)組（已經(jīng)有序） 以某個(gè)未知元素為支點(diǎn)做了旋轉(zhuǎn)灯帮，如：原數(shù)組 0124567 旋轉(zhuǎn)后得到 4567012 崖技。請(qǐng)找出旋轉(zhuǎn)后數(shù)組的最小值逻住。假定數(shù)組中沒(méi)有重復(fù)數(shù)字。
顯然把數(shù)組遍歷一遍就能找到最小值迎献，但是時(shí)間復(fù)雜度達(dá)到 O(n) 瞎访。有沒(méi)有更快的解決辦法？
問(wèn)題分析
旋轉(zhuǎn)之后的數(shù)組實(shí)際上可以劃分成兩個(gè)有序的子數(shù)組：前面子數(shù)組的大小都大于后面子數(shù)組中的元素吁恍；
用索引 left扒秸，right 分別指向首尾元素，元素不重復(fù)冀瓦。
若子數(shù)組是普通升序數(shù)組伴奥，則 A[left]<A[right]。
若子數(shù)組是循環(huán)升序數(shù)組（可以理解為兩不同的遞增序列）翼闽，前半段子數(shù)組的元素全都大于后半段子數(shù)組中的元素：A[left]>A[right]拾徙，計(jì)算中間位置 mid=(low+high)/2；
顯然感局， A[low…mid] 與 A[mid+1…h(huán)igh] 必有一個(gè)是循環(huán)升序數(shù)組尼啡，一個(gè)是普通升序數(shù)組。
若：A[mid]>A[high]询微，說(shuō)明子數(shù)組 A[mid+1,mid+2,…h(huán)igh] 循環(huán)升序崖瞭；更新 low=mid+1；
若：A[mid]<A[high] 拓提，說(shuō)明子數(shù)組 A[mid+1,mid+2,…h(huán)igh] 普通升序读恃；更新：high=mid隧膘。
Java代碼實(shí)現(xiàn):
public static int findMin(int a[]) {
int low = 0;
int high = a.length-1;
int mid;
while (low<high) {
mid = (low + high) / 2;
if (a[mid] < a[high]) {
high = mid;//最小值在左半部分
}else {
low = mid + 1;//最小值在右半部分
}
}
return a[low];
}
測(cè)試代碼：
public static void main(String[] args) {
int a[] = {6,7,0,1,2,3,4,5};
System.out.println(findMin(a));
}
輸出結(jié)果： 0
不管0在前半段還是后半段代态，總能正確輸出結(jié)果
