题解 | #旋转数组的最小数字#

旋转数组的最小数字：最直观的想法是，遍历一遍整个数组，使用Minx来获取最小值。

int minNumberInRotateArray(vector<int> rotateArray) {
        int Minx=INT_MAX;
        for(int i=0;i<rotateArray.size();i++)
            Minx=rotateArray[i]<Minx?rotateArray[i]:Minx;
        return Minx;
    }

优化：写完上述方法后我就有一个疑问，这样的方法适合任何一个数组，但是题目为什么特意强调旋转数组呢？是不是有什么信息尚未用到？于是我又看到了题目标签上写着“二分”，于是尝试了二分法。这里其实有一个误区，很多人可能认为二分只适合有序数组，事实上并不是这样的，当存在一个性质将数组分为两段后也是可以使用二分法的。比如，该题中，旋转数组是由原来的有序数组将一开始的若干个元素搬到数组末尾，那么就将数组分为了AB两部分，A是原数组末尾的部分，B是原数组开始的部分，可以得知A中的元素一定大于等于B中的元素。这时low指向数组开始，high指向数组末尾，当mid大于high时，那么mid一定属于A部分，这时最小的元素一定在区间[mid+1,high]中，反之当mid小于high时，那么mid一定属于B部分，这时最小的元素一定在区间[low,mid]中，注意mid也可能是最小元素，最后当mid等于high时，这时不确定是属于那一部分，于是将原来的二分转换为线性，即high--。

int minNumberInRotateArray(vector<int> rotateArray) 
{
   int low=0,high=rotateArray.size()-1;
   while(low<high)
   {
       int mid=low+(high-low)/2;
       if(rotateArray[mid]<rotateArray[high])
           high=mid;
       else if(rotateArray[mid]>rotateArray[high])
           low=mid+1;
       else
           high--;
    }
    return rotateArray[low];
}