旋轉(zhuǎn)數(shù)組的最小數(shù)字
前提摘要
關(guān)鍵找出規(guī)律：當(dāng)start指針和end指針?lè)謩e指向兩個(gè)相鄰元素時(shí)振湾，end指針指向的元素即為數(shù)組中最小數(shù)字款筑，論述見(jiàn)書(shū)本躏救。所以二分的目的最后還是縮小搜索范圍至兩個(gè)元素
問(wèn)題分解
我把可能出現(xiàn)的情況分成四種。
- 數(shù)組沒(méi)有經(jīng)過(guò)旋轉(zhuǎn)封救，此時(shí)
start指針剛好指向最小數(shù)字 - 數(shù)組發(fā)生了旋轉(zhuǎn)女气，旋轉(zhuǎn)后
end指針和start指針指向的剛好是相鄰的兩個(gè)遞增元素杏慰，start指針指向元素必定大于等于end指針指向元素。
將數(shù)組二分后炼鞠，根據(jù)邏輯判斷出最小數(shù)字要么在前半段（剛好中間的話先看作前半段）逃默，要么在后半段。
1）如果在前半段簇搅，那么start指針指向的元素必定大于middle指針指向的元素完域，因?yàn)?code>a[start]>a[end]且a[end]>a[middle]（遞增序列），使end指向middle的元素從而在前半段繼續(xù)查找
2）如果在后半段瘩将，同理吟税，end指針指向的元素必定小于middle指針指向的元素，因?yàn)?code>a[end]<a[start]且a[start]<a[middle]姿现，使start指向middle的元素從而在后半段查找
3）最后考慮極端的情況a[start]==a[middle]==a[end]肠仪，無(wú)法確定前半段還是后半段。我們要做的是打破這種“平衡”情況备典，可以修改start或者end异旧，同時(shí)引起middle的變化，使其回到上面兩種情況提佣。注意修改start或者end之后要求數(shù)組保持處于旋轉(zhuǎn)狀態(tài)吮蛹。假如修改了start那么有可能使數(shù)組處于完全遞增沒(méi)有經(jīng)過(guò)旋轉(zhuǎn)狀態(tài)，只能選擇修改end使其向前移動(dòng)一位
int findleastinspinSorted(int a[],int start,int end){
if (a==NULL || start>end){
cout<<"check your parameter"<<endl;
exit(1);
}
if (a[start]<a[end] || start==end){
return a[start];
}
int middle =0;
while(start!=end-1){
middle = (start + end)/2;
if(a[middle]<a[start]){
end = middle;
}else if (a[middle]>a[end]){
start = middle;
}else{
end--;
}
}
return a[end];
}
