[数据结构与算法]剑指Offer_旋转数组的最小值（图解二分查找）

原题链接

注意：直接遍历数组复杂度为O(N)不符合题目要求

基础分析

观察样例数组旋转后，数组可以看作两个排序后的子数组，而前面数组的元素都大于第二个数组。其中最小值正好位于两个数组的分界线，可以联想到二分法查找

一个指针指向数组的开始，一个指针指向数组的结束。第三个数组指向中间元素（begin+end)/2

根据二分思想如果arr[mid]对应的数字小于等于arr[end]，说明其在第二个数组中，让end=mid。如果arr[mid]大于等于arr[begin]说明其在第一个数组中，begin=mid。

特殊样例分析

1.输入数组为空或数组大小为1

在开始函数中需要判断数组大小，当大小为1时返回此元素即可

2.旋转了0个元素，即数组还是有序的。

此时最小元素为第一个元素。所以我们让mid的初值为begin（0）
当arr[begin]>=arr[end]时说明旋转元素>0在执行二分

3.因为重复元素导致无法区分中值是在那个数组的情况

代码实现

#include<assert.h>
class Solution {
public:
    int FindMin(vector<int>&arr)//顺序查找
    {
        int min=arr[0];
        for(int i=0;i<arr.size();i++)
        {
            if(arr[i]<min)
            {
                min=arr[i];
            }
        }
        return min;
    }
    int minNumberInRotateArray(vector<int> rotateArray) {
        assert(!rotateArray.empty());
        if(rotateArray.size()==1)
        {
            return rotateArray[0];
        }
        int begin=0;
        int end=rotateArray.size()-1;
        int mid=begin;//让mid刚开始=begin
        while(rotateArray[begin]>=rotateArray[end])//当不满足while情况时
        //说明数组没有旋转直接返回mid下标对应的数组的值
        {
            if(end-begin==1)
            {
                mid=end;
                break;
            }
            mid=(end+begin)/2;
            //当mid对应值个前后相同时，只能通过顺序查找
            if(rotateArray[begin]==rotateArray[mid]&&rotateArray[mid]==rotateArray[end])
            {
                return FindMin(rotateArray);
            }
            if(rotateArray[mid]>=rotateArray[begin])
            {
                begin=mid;
            }
            if(rotateArray[mid]<=rotateArray[end])
            {
                end=mid;
            }
        }
        return rotateArray[mid];
    }
};