C++算法之旋转数组的最小数字

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

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

我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还可以注意到最小的元素刚好是这两个子数组的分界线。我们试着用二元查找法的思路在寻找这个最小的元素。

int MinInOrder(int array[], int i, int j)
{
	int result = array[i];
	for (int m = i+1; m <= j;m++)
	{
		if (array[m] < result)
		{
			result = array[m];
		}
	}

	return result;
}
int Min(int array[], int nlength)
{
	if (array == NULL || nlength < 0)
	{
		throw new std::exception("Invalid parameters");
	}

	int index1   = 0;
	int index2   = nlength - 1;
	int indexMid = index1;
	while (array[index1] >= array[index2])
	{
		
		indexMid = index1+ (index2 - index1)/2;

		//indexMid = (index1+index2)/2;


		//如果三个数相等，那么只能顺序查找
		if (array[index1] == array[index2] && array[index2] == array[indexMid])
		{
			return MinInOrder(array,index1,index2);
		}

		//如果中间的数字大于开头的index1，那么最小的数字一定在这个中间数的后面，令index1=mid这个中间数
		if(array[indexMid] >= array[index1])
		{
			index1 = indexMid;
		}
		//如果中间的数字小于结尾的index2，那么最小的数字一定在这个中间数字的前面，令index2=mid
		else if(array[indexMid] <= array[index2])
		{
			index2 = indexMid;
		}
		//当index1与index2相差为1 的时候，最小的数就是index2；
		if (index2 - index1 == 1)
		{
			indexMid = index2;
			break;
		}
	}
	return array[indexMid];
}

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

C++算法之旋转数组的最小数字