【剑指offer】旋转数组的最小数字

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

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

旋转数组中包含两个递增排序的子数组，有阴影背景的是第二个子数组。

如下图所示：

技术分享

(1)把Pl指向数组的第一个数字，P2指向数组的最后一个数字。由于Pl和P2中间的数字5大于P1指向的数字，中间的数字在第一个子数组中。下一步把P1指向中间的数字。

(2) Pl和P2中间的数字1小于P2指向的数字，中间的数字在第二个子数组中。下一步把P2指向中间的数字。

(3)P1和P2指向两个相邻的数字，则P2指向的是数组中的最小数字。

技术分享

当两个指针指向的数字及它们中间的数字三者相同的时候，我们无法判断中间的数字是位于前面的子数组中还是后面的子数组中，也就无法移动两个指针来缩小查找的范围。此时，我们不得不采用顺序查找的方法。

完整代码如下：

//获得旋转数组的最小数字
int GetMinNumber(int *numbers, int length)
{
	if (numbers==NULL||length<0)
	{
		printf("parameters error!");
	}
	int start=0;
	int end=length-1;
	int mid=start;
	while(numbers[start]>=numbers[end])
	{
		if (end-start==1)
		{
			mid=end;
			break;
		}
		mid=(start+end)/2;
		//如果下标start, mid ,end所指向的数字相等，只能顺序查找
		if(numbers[start]==numbers[mid]&&numbers[mid]==numbers[end])
			return MinInOrder(numbers, start, end);
		//中间值>=p1（start)所指向的值
		if (numbers[mid]>=numbers[start])
		{
			start=mid;
		}
		//中间值<=p2(end)所指向的值
		else if (numbers[mid]<=numbers[end])
		{
			end=mid;
		}
	}
	return numbers[mid];
}


//返回数组a的最小元素
int MinInOrder(int *a, int idx1, int idx2)
{
	int minValue=a[idx1];
	for (int i=idx1; i<idx2; i++)
	{
		if (minValue>a[i])
		{
			minValue=a[i];
		}
	}
	return minValue;
}

转载请注明出处：http://blog.csdn.net/lsh_2013/article/details/45603031

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

【剑指offer】旋转数组的最小数字