【剑指offer】面试题八：旋转数组的最小数字

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

解法一：

　这道题最直观的解法就是遍历一遍数组，这样我们就能找到最小的元素。这种思路的时间复杂度显然是 O(n)。

代码如下：

// findMin.c
#include "stdio.h"
#include "stdlib.h"

#define N 5

int findMin(int *arr, int len)
{
    int minVal = arr[0], i;

    for(i = 1; i < len; i++)
    {
        if(minVal > arr[i])
            minVal = arr[i];
    }
    return minVal;
}

int main(int argc, char *argv[])
{
    int arr[N] = {3,4,5,1,2};

    int minNum = findMin(arr, N);
    printf("The min Num is: %3d",minNum);

    return 0;
}

但是这个思路没有利用输入的旋转数组的特性，那么有没有效率更好地办法呢？

解法二：

　1、旋转时候的数组实际上可以划分为两个排序的子数组，而前面的子数组的元素都大于或者等于后面子数组的元素。

　2、最小的元素刚好是这两个子数组的分界线。

　3、第一个元素值应该是大于或者等于最后一个元素的。

在已经有序的数组中我们可以用二分查找法实现 O(log n)的查找，而旋转数组在一定程度上是排序的，因此我们可以试着用二分查找法的思路来寻找这个最小的元素。

分析：

　1、我们用两个指针pHead，pTail分别指向数组的第一个元素和最后一个元素，根据二分查找的规则，我们可以找到指向数组中间的元素的指针pMid。

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

　3、如果中间元素*pMid位于后面的递增子数组，那么它应该小于或者等于最后一个指针pTail指向的元素。此时数组中最小的元素应该位于*pMid的前面。这样我们就可以把最后一个指针pTail指向*pMid。而移动之后的pTail仍然位于后面的递增子数组中。

　4、不管是移动 pHead 和 pTail，查找的范围都会缩小到原来的一半。接下来我们再用更新之后的两个指针，重复做新一轮的查询。

　按照上述思路，第一个指针总是指向前面的递增数组的元素，而第二个指针总是指向后面递增数组的元素。最终第一个指针将指向前面子数组的最后一个元素，而第二个指针会指向后面子数组的第一个元素。也就是说，第一个指针与第二个指针最终会指向两个相邻的元素。这就是循环结束的条件。

　可以以数组{3,4,5,1,2}为例，画图试着分析。

　基于这个思路，我们写出如下的代码：

// findMin.cpp
#include "stdio.h"
#include "stdlib.h"
#include <stdexcept>

#define N 5

int findMin(int *arr, int len)
{
    if(arr == NULL || len <= 0)
        throw std::out_of_range("Invalid parameters");

    int pHead = 0;
    int pTail = len - 1;

    while(pHead < pTail)
    {
        if(pTail - pHead == 1)
            break;

        int mid = (pHead + pTail) / 2;
        if(arr[mid] >= arr[pHead]) // 前半部分
            pHead = mid;
        else if(arr[mid] <= arr[pTail])
            pTail = mid;
    }

    return arr[pTail];
}

int main(int argc, char const *argv[])
{
    int arr[N] = {3, 4, 5, 1, 2};

    int minVal = findMin(arr, N);
    printf("The min num is: %d
", minVal);

    return 0;
}

但是上面仍存在例外情况：

考虑数组 {1,0,1,1,1}、{1,1,1,0,1}

　pHead　　　mid　　　　pTail

① { 1,　　0,　  1,　　1,　　1}

根据上面的解法，此时arr[pHead] = 1、arr[pTail] = 1、arr[mid] = 1；

由语句 if(arr[mid] >= arr[pHead])  pHead = mid;  可知pHead将移动到 mid 所在的位置，而最小元素 0 位于数组的前半部分，这样就脱离了更新后的 pHead（mid） 与 pTail 的查找范围，这样就找不到最小元素 0 了。

 ② { 1,　　1,　  1,　　0,　　1} 与 ① 类似；

因此，在arr[pHead] = arr[pTail] == arr[mid] 的情况下，我们只能遍历数组进行查找了。

完整的代码如下：

// findMin.cpp
#include "stdio.h"
#include "stdlib.h"
#include <stdexcept>

#define N 5

int seqSearch(int *arr, int len) // 顺序查找
{
    int minVal = arr[0], i;

    for(i = 1; i < len; i++)
    {
        if(minVal > arr[i])
            minVal = arr[i];
    }
    return minVal;
}

int findMin(int *arr, int len)
{
    if(arr == NULL || len <= 0)
        throw std::out_of_range("Invalid parameters");

    int pHead = 0;
    int pTail = len - 1;

    while(pHead < pTail)
    {
        if(pTail - pHead == 1)
            break;

        int mid = (pHead + pTail) / 2;
        if(arr[mid] == arr[pHead] && arr[mid] == arr[pTail]) // 三者相等，顺序查找
            return seqSearch(arr, len);

        if(arr[mid] >= arr[pHead]) // 前半部分
            pHead = mid;
        else if(arr[mid] <= arr[pTail]) // 后半部分
            pTail = mid;
    }

    return arr[pTail];
}

int main(int argc, char const *argv[])
{
    int arr[N] = {3, 4, 5, 1, 2};
    int minVal = findMin(arr, N);
    printf("1、The arr's min num is: %d
", minVal);

    int arr2[N] = {1, 0, 1, 1, 1};
    int minVal2 = findMin(arr2, N);
    printf("2、The arr2's min Num is: %d
", minVal2);

    return 0;
}

编译与执行：

g++ -0 findMin findMin.cpp
./findMin

本文完。