学步园

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

针对上面的问题，我们很清楚的知道，输入数组的前半部分和后半部分都是有序的，并且前半部分>=后半部分。根据这样的特性我们就行写出代码。

//求出一个数组中的拐点  length是数组的长度
int getDot(int data[],int length)
{
	if(data==NULL)
		return 0;

	int i=0,j=length-1;
	int flag=false;
	while(i<j)
	{
		if(data[i]>data[j])
		{
			i++;
		}
		else if(data[i]<data[j])
		{
			j--;
		}
		else if(data[i]==data[j])
		{
			i++;
			j--;
		}
	return i;
}

上面返回的是拐点的位置。

这样写有没有问题呢？

下面我们来写个测试用例你就知道了！

比如A={1,1,1,1,0,0,1}; 你会发现输出的位置是5，不是第一个0的位置。

我们要怎么来完善上面的程序呢？

如下：

//求出一个数组中的拐点  length是数组的长度
int getDot(int data[],int length)
{
	if(data==NULL)
		return 0;

	int i=0,j=length-1;
	int flag=false;
	while(i<j)
	{
		if(data[i]>data[j])
		{
			i++;
		}
		else if(data[i]<data[j])
		{
			j--;
		}
		else if(data[i]==data[j])
		{
			i++;
			j--;
			flag=true;
		}
		if(flag&&data[i]<data[i-1])//一旦发现这个情况，就使我们找的拐点，这个也考虑了重复情况
			return i;
	}
	return i;
}

flag用于判断数组中的是否有相同的元素。
这样基本上就完善了！

如有问题请批评指正哈！