《剑指offer》--011--旋转数组中的最小数字

《剑指offer》–目录索引

题目：

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

思路：

最简单直接的方法就是顺序查找，时间复杂度为0(n)，但是这样就没有用到旋转数组的特性了，而且这道题的最优解法的时间复杂度是接近O(log n)的；因此，首先来梳理一下旋转数组的特性：
①无重复数字的旋转数组：第一个数字一定大于最后一个数字；
②有重复数字的旋转数组：第一个数字大于或等于最后一个数字；
③旋转数组以最小值为中界值将数组分成左右两个升序的数组；
④以第一个数字的下标left和最后一个数字的下标right开始向中间靠拢，类似二分查找；中间数字的下标为mid=(left+right)/2；
⑤如果arr[left] <= arr[mid],说明中间值属于左半边升序数组，则left=mid;
否则，如果arr[right] >= arr[mid]，说明中间值仍属于右半边升序数组,则right=mid;
⑥当left和right相邻，则代表已找到，arr[right]就是最小值，如动图：

特殊情况：
数组{1，0，1，1，1}是数组{0，1，1，1，1}的一个旋转，如下图：

left下标的数字是1，right下标的数字是1，mid下标的数字也是1，像这种情况就无法分出mid所指的1到底属于左半边数组还是右半边数组，因此当三个下标所指向的数字相同时，只能用顺序查找了。

代码：

int MinInArray(int* arr,int left,int right)//顺序查找
{
    int result=arr[left];
    int i=left+1;
    for(;i <= right;i++)
    {
        if(result > arr[i])
        {
            result =arr[i];
        }
    }
    return result;
}

int MinInOrder(int* arr,int length)//旋转数组中的最小值
{
    assert(arr && length > 0);//断言，不能传空指针以及数组大小必须大于0
    if(length == 1)//如果数组就一个元素，最小值就是它本身
    {
        return arr[0];
    }
    int left=0;
    int right=length-1;
    int mid=left;

    while(arr[left] >= arr[right])//左半边数组的值要大于右半边数组的值
    {
        if(right-left == 1)//如果left和right相邻，代表找到了
        {
            mid=right;
            break;
        }
        mid=(left+right)>>1;

        if(arr[left] == arr[mid] && arr[right] == arr[mid])//当三个下标所指向的值相同时，只能用顺序查找了
        {
            return MinInArray(arr,left,right);
        }

        if(arr[left] <= arr[mid])
        {
            left=mid;
        }
        else if(arr[right] >= arr[mid])
        {
            right=mid;
        }
    }
    return arr[mid];
}

测试代码：

void test1()// 典型输入，单调升序的数组的一个旋转
{
    int arr[]={3,4,5,1,2};
    int sz=sizeof(arr)/sizeof(arr[0]);
    printf("%d\n",MinInOrder(arr,sz));
}

void test2()// 有重复数字，并且重复的数字刚好的最小的数字
{
    int arr[]={3,4,5,1,1,2};
    int sz=sizeof(arr)/sizeof(arr[0]);
    printf("%d\n",MinInOrder(arr,sz));
}

void test3() // 有重复数字，但重复的数字不是第一个数字和最后一个数字
{
    int arr[]={3,4,5,1,2,2};    
    int sz=sizeof(arr)/sizeof(arr[0]);
    printf("%d\n",MinInOrder(arr,sz));
}

void test4()// 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字
{
    int arr[]={1,0,1,1,1};
    int sz=sizeof(arr)/sizeof(arr[0]);
    printf("%d\n",MinInOrder(arr,sz));

}

void test5() // 单调升序数组，旋转0个元素，也就是单调升序数组本身
{
    int arr[]={1,2,3,4,5};
    int sz=sizeof(arr)/sizeof(arr[0]);
    printf("%d\n",MinInOrder(arr,sz));
}

void test6() // 数组中只有一个数字
{
    int arr[]={2};
    int sz=sizeof(arr)/sizeof(arr[0]);
    printf("%d\n",MinInOrder(arr,sz));
}

void test7() // 数组中只有一个数字
{
    printf("%d\n",MinInOrder(NULL,0));
}

int main()
{
    test1();
    test2();
    test3();
    test4();
    test5();
    test6();
    test7();
    return 0;
}

运行结果：