剑指offer：求一个旋转数组中的最小值

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

考虑的特殊情况：

1、功能测试：输入的数组是升序排序的一个旋转，数组中有重复的数字或者没有重复的数字

2、边界值测试：输入的数组是一个升序排序的数组，只包含一个数字的数组

3、特殊输入测试（输入一个NULL指针）

正常的思路：

一般而言，拿到这个题目，我们通常的想法就是，一个指针指向开始的元素，向后遍历，如果遇到第一个比开始元素小的值就是我们所求的最小值，这是由于旋转数组的性质决定的。

但是这种做法虽然保险，但是复杂度仍然是O(n)，显然我们并不提倡。因为这并没有完全应用旋转数组的性质来解题

方法：

因为旋转数组是一个升序数组将前面的一段移到后面所形成的，则实际上旋转数组分成前后两段，这两段都是升序的，而且后一段的最大值不大于前一段的最小值。于是我们可以用二分查找法，只不过此时过程要变一下。

1、确定low表示数组首元素下标，high表示数组尾元素下标，mid=(low+high)/2，

2、如果A[low]<=A[mid]，则此时mid所表示的元素一定在前一段里，而最小值一定在后一段中，则令low=mid，继续下去

3、如果A[mid]<=A[high]，则此时mid所表示的元素一定在后一段里，而最小值在mid之前后者就是mid，则令high=mid

4、递归终止条件是low+1=high。

但是我们也要记住特殊的情况，就是A[low]==A[high]&&A[mid]==A[high]，例如{1，0，1，1，1}或者{1，1，1，0，1}，此时我们没有其他好的办法，只好回归到正常的思路，就是从开始向后遍历。

下面是源程序的代码：

#include<stdio.h>

int min(int A[],int low,int high);
int rotateMin(int A[],int low,int high)
{
    int mid=(low+high)/2;
    if(low+1==high)return high;
    else
    {
        if(A[low]==A[high]&&A[low]==A[mid])return min(A,low,high);
        if(A[low]<=A[mid])return rotateMin(A,mid,high);
        if(A[mid]<=A[high])return rotateMin(A,low,mid);
    }
}
int min(int A[],int low,int high)
{
    int i=low,tag=0;
    for(;i<=high;++i)
    {
        if(A[low]>A[i])
        {
            tag=1;
            break;
        }
    }
    if(tag==0)return A[low];
    else return i;
}
int main()
{
    printf("请输入旋转数组的长度!\n");
    int n=0;
    scanf("%d",&n);
    int arr[n];
    int i=0;
    for(i=0;i<n;++i)
        scanf("%d",&arr[i]);
    if(n-1==0 || arr[0]<arr[n-1])
    {
        printf("\n旋转数组中最小的值为:%d\n",arr[0]);
        exit(0);
    }
    printf("\n旋转数组中最小的值为:%d\n",arr[rotateMin(arr,0,n-1)]);
    return 0;
}                                                                                                                                        

下面是运行结果：

剑指offer：求一个旋转数组中的最小值,布布扣,bubuko.com
剑指offer：求一个旋转数组中的最小值
原文：http://blog.csdn.net/litianpenghaha/article/details/22103073