旋转数组的最小数字
前提摘要
关键找出规律：当start指针和end指针分别指向两个相邻元素时，end指针指向的元素即为数组中最小数字，论述见书本。所以二分的目的最后还是缩小搜索范围至两个元素
问题分解
我把可能出现的情况分成四种。
- 数组没有经过旋转，此时
start指针刚好指向最小数字 - 数组发生了旋转，旋转后
end指针和start指针指向的刚好是相邻的两个递增元素，start指针指向元素必定大于等于end指针指向元素。
将数组二分后，根据逻辑判断出最小数字要么在前半段（刚好中间的话先看作前半段），要么在后半段。
1）如果在前半段，那么start指针指向的元素必定大于middle指针指向的元素，因为a[start]>a[end]且a[end]>a[middle]（递增序列），使end指向middle的元素从而在前半段继续查找
2）如果在后半段，同理，end指针指向的元素必定小于middle指针指向的元素，因为a[end]<a[start]且a[start]<a[middle]，使start指向middle的元素从而在后半段查找
3）最后考虑极端的情况a[start]==a[middle]==a[end]，无法确定前半段还是后半段。我们要做的是打破这种“平衡”情况，可以修改start或者end，同时引起middle的变化，使其回到上面两种情况。注意修改start或者end之后要求数组保持处于旋转状态。假如修改了start那么有可能使数组处于完全递增没有经过旋转状态，只能选择修改end使其向前移动一位
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];
}
