面试题11：旋转数组

把一个数组最开始的若干个元素搬到数组的末尾，成为数组的旋转。输入一个递增排序的数组的一个旋转，输出数组的最小元素。

解析：这题最容易想到的就是顺序搜索一遍，但是这样子的时间复杂度在 O(n)。我们可以用类似二分的思想来找到那个最小的元素，但是有一种特殊情况会让我们必须使用顺序查找，因为在这个特殊情况下无法判断是要往左半部分查找还是右半部分查找。

先想一下如何使用二分查找。我们把被旋转到末尾的那个小的递增片段计作 a，由于旋转作用而向前挪动了的剩下的那个递增片段计作 b。例如，原有片段是 {1,2,3,4,5,6,7,8}，我把 {1,2,3} 旋转到后面，那么旋转后就变成了 {4,5,6,7,8,1,2,3}。这个时候，a={1,2,3}，b={4,5,6,7,8}。我们在二分查找的时候，中间位置上的数字有可能落在 a 里，也有可能落在 b 里。如果落在 a 里面，那么最小的数字应该还在中间数字的左边。如果落在 b 里，最小的数字应该在中间数字的右边。用这个思想我们就可以不断的去逼近最小的数字。多写几个例子，模拟一边过程，你就会发现最后中间的数字指向的就是最小的数字。

我们考虑几种特殊情况。首先，当前比较的数组已经递增了。那么这个时候数组的第一位就是最小的数字，我们可以直接返回。我们可以把中间位的初始值设定为第一位，在每次进入循环的时候检查该数组是否已经递增。如果已经递增，就不需要进入循环了，直接返回第一位就好。然后是我刚说到的，无法使用二分查找的方法。考虑 {0,1,1,1,1}，旋转前四位得到 {1,0,1,1,1}。开头、中间和结尾的位置都是1，那这个时候就无法判断要往左边走还是往右边走了。如果遇到了这个情况，那么只能顺序搜索当前序列，找到最小的元素。

答案：

int MinInOrder(int* numbers, int index1, int index2)
{
    int result = numbers[index1];
    for(int i = index1 + 1; i <= index2; ++i)
    {
        if(result > numbers[i])
            result = numbers[i];
    }

    return result;
}

int Min(int* numbers, int length)
{
    if(numbers == nullptr || length <= 0)
        throw exception();

    int first = 0, last = length-1;
    int mid = first; //将中间位初始为第一位
    while (numbers[first]>=numbers[last]) //如果该序列本身就是递增序列，退出 while
    {
        if (last-first == 1)
        {
            mid = last;
            break;
        }
        else
        {
            mid = first + ((last-first)>>1);
            if (numbers[first]==numbers[mid] && numbers[mid]==numbers[last])
                return MinInOrder(numbers, first, last);
            else
            {
                if (numbers[mid]>=numbers[first])
                    first = mid;
                else if (numbers[mid]<=numbers[first])
                    last = mid;
            }
        }
    }
    return numbers[mid];
}