剑指OFFER面试题8：旋转数组的最小数字

旋转数组的最小数字

前提摘要

关键找出规律：当start指针和end指针分别指向两个相邻元素时，end指针指向的元素即为数组中最小数字，论述见书本。所以二分的目的最后还是缩小搜索范围至两个元素

问题分解

我把可能出现的情况分成四种。

1. 数组没有经过旋转，此时start指针刚好指向最小数字
2. 数组发生了旋转，旋转后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];
}