剑指offer面试题：旋转数组的最小数字。_对于旋转数组,两部分分别递增且不重复, 找出最小值最少需要访问数组中的几个元素

        题目要求：找出一个旋转数组中的最小值（所谓旋转数组就是把一个递增的数组找出若干个连续元素搬到末尾，比如数组{1，2，3，4，5}的旋转数组可以是{4，5，1，2，3}
     

       普遍思路：大家刚看到这道题的第一反应应该是遍历逐个数组找出最小值，这样做当然可以解决这道题，但有个缺点就是时间复杂度为O（n），并且没有用到题目给出的旋转数组的递增特性。所以我们可以另辟蹊径找到新方法

       思路pro：我们可以根据数组部分有序的特性使用二分查找，相当于把数组分为两部分递增序列，4，5为第一部分，后面的1，2，3为第二部分。然后设置两个指针分别指向第一个元素和最后一个元素，再设置一个变量保存数组中间值，然后分别与第一个元素和第二个元素比较，如果第一个元素比中间的那个数大，那么说明最小值在第二部分，所以这时候把第一个指针指向中间，另一个指针不变，如果第一个指针比中间值小，说明最小值在第一部分，这时候把第二个指针指向中间值。最终两个指针会相邻，相邻时第二个指针的指向肯定就是最小值。这就是类似于二分查找的解法。

代码如下

#include<vld.h>
#include<iostream>
int special(int *arr,int a,int b);
 
int sort(int *arr,int n)
{
	if(arr==NULL || n<=0)//判断形参合法性
	{
		throw std:: exception("input error");
	}
	int start=0;
	int end=n-1;
	int mid;
	while(arr[start]>=arr[end])
	{
		if(start+1==end)
		{
			break;
		}
		mid=(start+end)/2;
		if(arr[start]==arr[end]==arr[mid])//针对例如10111这种特例，只能顺序查找
		{
			return special(arr,start,end);
		}
		if(arr[start]>=arr[mid])
		{
			end=mid;
		}
		if(arr[start]<arr[mid])
		{
			start=mid;
		}
	}
	return arr[end];
}
int special(int *arr,int a,int b)//顺序查找
{
	int min=arr[a];
	for(int i=1;i<b;i++)
	{
		if(arr[i]<min)
		{
			min=arr[i];
		}
	}
	return min;
}
int main()
{
	int n;
	printf("请输入数组长度\n");
	scanf("%d",&n);
	int *arr=new int[n];
    printf("请输入数组\n");
	for(int i=0;i<n;i++)
	{
		scanf("%d",&arr[i]);
	}
	int*brr=NULL;
	int m=sort(arr,n);
	printf("最小值为%d",m);
	delete arr;
}