剑指offer—旋转数组的最小数字

浏览数：29 / 时间：2015年06月08日

题目：

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

例如数组（3,4,5,1,2）位{1,2,3,4,5}的一个旋转，该数组的最小值为1.

基本思想：

二分查找，p1指向a[0],p2指向a[len-1]。如果a[mid]>a[p1]，则最小值在后半段，p1=mid；如果a[mid]<a[p2]，则最小值在前半段，p2=mid。

特殊情况：

技术分享

注意：在这两个数组中，第一个数字、最后一个数字和中间数字都是1，我们无法确定中间的数字1属于第一个递增字数组还是属于第二个递增字数组。

这种情况只能顺序查找的方法。

#include <iostream>
using namespace std;

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

int min(int a[],int len)
{
	if(len<0)
		return 0;

	int index1=0;
	int index2=len-1;
	int indexMid=index1;//如果旋转数组是它本身，则默认是index1

	while(a[index1]>=a[index2])
	{
		if(index2-index1==1)
		{
			indexMid=index2;
			break;
		}

		indexMid=(index1+index2)/2;

		//如果index1，index2和indexMid三数相等，则只能顺序查找
		if(a[index1]==a[index2]&&a[indexMid]==a[index1])
			return MinInOrder(a,index1,index2);

		if(a[indexMid]>=a[index1])
			index1=indexMid;
		else if(a[indexMid]<=a[index2])
			index2=indexMid;
	}

	return a[indexMid];
}

int main()
{
	int a[]={3,4,5,1,2};
	int b[]={1,0,1,1,1};

	cout<<min(a,5)<<endl;
	cout<<min(b,5)<<endl;

	return 0;
}