剑指offer 11 旋转数组找最小值

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

我的思路是分情况讨论, 看首元素和尾元素的大小关系:

1. 首<尾, 一定是单调递增的序列, 那么直接返回第一个
2. 首>尾, 一定产生了旋转, 并且最小值一定从尾处的n个里面里找, 这个时候可以用二分法(但其实是一个修改的二分法, 跳出条件是[low, high]区间长度为2,此时拿出high元素. 因此不会产生high<low)
3. 首尾相同, 那么这种情况包含了相同元素的序列 / 先增后平 / 两个增序列的可能. 想区分这三种, 除非全部遍历元素, 那么这种情况没有优化必要.

int minArray(int* numbers, int numbersSize){
    if(numbersSize == 0) return 0;
    if(numbersSize == 1) return 1;

    //递增序列返回第一个
    if(numbers[0] < numbers[numbersSize-1]) return numbers[0];

    //肯定发生了旋转,且收尾不相同
    else if(numbers[0] > numbers[numbersSize-1])
    {
        int low = 0, high = numbersSize - 1, mid;
        while(low < high)
        {
            if(low + 1 == high)
            {
                return numbers[high];
            }
            mid = (low + high) / 2;
            if(numbers[mid] <= numbers[high]) high = mid;
            else if(numbers[mid] >= numbers[low]) low = mid;
        }
    }

    //首尾相同, 存在三种可能:1:平线, 2:两个上升  3:上升和平线
    else{
        int low = 0;
        while(low < numbersSize-1)
        {
            if(numbers[low] > numbers[low+1]) return numbers[low+1];
            low++;
        }
        return numbers[low];
    }
    

    return 0;
}