面试题11：旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

方法1：思路如书上：前半部分和后半部分都是有序序列，根据这个特点进行二分查找，要点如下：

用两个指针first、last指向数组第一个元素和最后一个元素，据此找到数组的中间元素mid;
将array[mid]分别与array[first]、array[last]比较：
若array[mid]>=array[first]，则array[mid]应位于mid前面的递增子数组,令first=mid;
若array[mid]<=array[last]，则array[mid]应位于mid后面的递增子数组，令last=mid；
当移动到first+1=last时，循环结束，array[first]即为最大元素，array[last]即为最小元素。
但是这个思路有两个漏洞：一是无法解决原递增序列，例如1,2,3,4,5。二是无法解决类似1,0,1,1,1这样first,mid,last都相等的序列。
为解决问题1，思路是：在前面两步之前，保留array[0]的值，1,2步中判断若array[first]<=array[last]进入循环，若为递增序列，array[first]<array[last]不满足循环，直接返回array[0]的值；
为解决问题2，思路是：在1,2步while循环中判断first,mid,last三处值是否相等，若是，则进行顺序查找。

代码：

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

int sequenceSearch(vector<int> array)
{
    int minData = array[0];
    for (int i = 1; i < array.size() - 1; i++)
    {
        if (minData > array[i])
            minData = array[i];
    }
    return minData;
}

int minNumberInRotateArray(vector<int> rotateArray) 
    {
        int length = rotateArray.size();
        if (length <= 0)
            return 0;
        //定义两个指针:first指向前半部分有序数组的第一个，last指向后半部分有序数组的最后一个
        int first = 0, last = length - 1;
        /*
        若array[mid]>=array[first]，则断定mid位于前半部分，令first=mid;
        若array[mid]<=array[last],则断定mid位于后半部分，令last=mid;
        当first与last相邻时，last所指即为最小值，first所指即为最大值。
        */
        /*
        修改1：上述思路假定数组一定有旋转，即array[first]>array[last],则这个有序数组就是从小到大排列的
        测试原排序数组如0,1,2,3,4，则结果不正确，所以得修改
        */
        int minData = rotateArray[0];
        while (rotateArray[first]>=rotateArray[last])
        {
            int mid = (first + last) / 2;
            if(first==last-1)
            {
                minData = rotateArray[last];
                break;
            }
            /*
            修改2：若碰见类似1,0,1,1,1,数组时，数组在first,mid,last三个位置数字都相等，
            这样就无法判断mid属于前半部分还是后半部分导致错误，所以这种情况得顺序查找了
            */
            if (rotateArray[first] == rotateArray[mid] && rotateArray[mid] == rotateArray[last])
            {
                return sequenceSearch(rotateArray);
            }
            if (rotateArray[mid] >= rotateArray[first])
                first = mid;
            if (rotateArray[mid] <= rotateArray[last])
                last = mid;
        }
        return minData;
    }

int main()
{
    vector<int> array = {1,0,1,1,1};
    int minData = minNumberInRotateArray(array);
    cout << minData;
    return 0;
}

方法2：二分查找（力扣）

https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-by-leetcode-s/

int minArray(vector<int>& rotateArray) {
        if (rotateArray.empty())
            return 0;
        int left = 0, right = rotateArray.size() - 1;
        while (left<right)
        {
            //记录最右边元素为x，位于最小值左侧元素均大于等于x，位于最小值右侧元素均小于等于x。
            int x = rotateArray[right];
            size_t mid = left + (right - left) / 2;
            /*若中间元素小于x，说明中间元素位于最小值右侧范围，所以最小值位于中间元素左侧,可以抛弃                    中间元素右边部分元素，
             注意这个地方不能写成right=mid-1。因为此时mid所指元素处于较小方，可能它就是那个最小的元素，所以不能忽略它*/
            if (rotateArray[mid] < x)
                right = mid;
            //若中间元素大于x，则说明中间元素位于最小值左侧，抛弃位于最小值左侧的部分元素
            else if (rotateArray[mid] > x)
                left = mid+1;
            //若中间元素==x，无法判断中间元素位于最小值左侧还是右侧，就只抛弃最右边的x即可，再一步步寻找
            else
                right -= 1;
            cout << left << " " << right << endl;
        }
        return rotateArray[left];
    }