旋转数组的最小数字

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

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

思路：我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还注意到最小的元素刚好是这两个子数组的分界线。在排序的数组中没我们可以用二分法实现O(logn)的查找。我们用两个指针分别指向数组的第一个元素和最后一个元素，按照旋转规则，第一个元素大于或者等于最后一个元素。

接着我们可以找到数组中间的元素。如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素位于该之间元素的后面。我们可以把第一个指针指向该之间元素，这样就可以缩小寻找范围，移动之后的第一个指针仍然位于前面的递增数组。

同样，如果该中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时数组中最小的元素位于该之间元素的前面。我们可以把第二个指针指向该之间元素，这样就可以缩小寻找范围，移动之后的第二个指针仍然位于前面的递增数组。

对于特殊情况，如下面的情况，就需要利用顺序查找。对于数组{0,1,1,1,1}的旋转。

１	０	１	１	１
p1		Mid		p2

１	1	１	0	１
p1		Mid		p2

#include <iostream>
#include <cstdio>
#include <exception>
using namespace std;

int MinInOrder(int* numbers, int index1, int index2);

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

    int index1 = 0;
    int index2 = length-1;
    int Mid = index1;
    while(numbers[index1] >= numbers[index2])
    {
        // 如果index1和index2指向相邻的两个数，
        // 则index1指向第一个递增子数组的最后一个数字，
        // index2指向第二个子数组的第一个数字，也就是数组中的最小数字
        if(index2 - index1 == 1)
        {
            //index2指向的是最小的数字
            Mid = index2;
            break;
        }
        Mid = (index1 + index2)/2;

        // 如果下标为index1、index2和indexMid指向的三个数字相等，
        // 则只能顺序查找
        if(numbers[index1] == numbers[index2] && numbers[index1] == numbers[Mid])
            return MinInOrder(numbers, index1, index2);

        if(numbers[Mid] >= numbers[index1])
            index1 = Mid;
        else if(numbers[Mid] <= numbers[index2])
            index2 = Mid;

    }
    return numbers[Mid];
}

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

// ====================测试代码====================
void Test(int* numbers, int length, int excepted)
{
    int result = 0;
    try
    {
        result = Min(numbers, length);

        for(int i=0; i<length; i++)
            printf("%d ", numbers[i]);

        if(result == excepted)
            printf("\tPassed.\n");
        else
            printf("\tFailed.\n");
    }
    catch(...)
    {
        if(numbers == nullptr)
            printf("Test Passed.\n");
        else
            printf("Test Failed.\n");
    }
}

int main()
{
    // 典型输入，单调升序的数组的一个旋转
    int array1[] = { 3, 4, 5, 1, 2 };
    Test(array1, sizeof(array1) / sizeof(int), 1);

    // 有重复数字，并且重复的数字刚好的最小的数字
    int array2[] = { 3, 4, 5, 1, 1, 2 };
    Test(array2, sizeof(array2) / sizeof(int), 1);

    // 有重复数字，但重复的数字不是第一个数字和最后一个数字
    int array3[] = { 3, 4, 5, 1, 2, 2 };
    Test(array3, sizeof(array3) / sizeof(int), 1);

    // 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字
    int array4[] = { 1, 0, 1, 1, 1 };
    Test(array4, sizeof(array4) / sizeof(int), 0);

    // 单调升序数组，旋转0个元素，也就是单调升序数组本身
    int array5[] = { 1, 2, 3, 4, 5 };
    Test(array5, sizeof(array5) / sizeof(int), 1);

    // 数组中只有一个数字
    int array6[] = { 2 };
    Test(array6, sizeof(array6) / sizeof(int), 2);

    // 输入nullptr
    Test(nullptr, 0, 0);

    return 0;
}