学步园

69.旋转数组中的最小元素。
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个
排好序的数组的一个旋转，
输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数
组的最小值为 1。
分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，时间复

杂度显然是 O(N)。但这个思路没有利用输入数组的特性，我们应该能找到更好的解法。

/*
69.旋转数组中的最小元素。
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个
排好序的数组的一个旋转，
输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数
组的最小值为 1。
分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，时间复
杂度显然是 O(N)。但这个思路没有利用输入数组的特性，我们应该能找到更好的解法。

类似与移动数组的二分查找问题
*/
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int searchMin(int a[],int n)
{
	int mid,left,right;
	left=0;
	right=n-1;
	while(left<=right)
	{
		mid=(left+right)/2;
		if(left+1==right)
			return a[left]>a[right]?a[right]:a[left];
		
		if(a[mid]<=a[right])//右分区单调递增，最小值mid
			right=mid;
		else if(a[left]<=a[mid])//左分区递增 右分区非单调递增， 
			left=mid;
	} 
}

int helper(int a[],int s,int t) //原来是递增序列 
{
	if(s==t||a[s]<a[t])//原来是递增序列 左<右 直接返回左 
		return a[s];
	int m=(s+t)/2;
	if (a[s]>a[m]) //左边>中间 说明右边是正常的升序 左边存在断点：最小值 
		return helper(a,s,m);
	else
		return helper(a,m+1,t);
}

int searchMin2(int a[], int n) 
{
	return helper(a,0,n-1);
}

int  main()
{
	int num;
	
	while(cin>>num,num)
	{
		int *a=new int[num];
		for(int i=0;i<num;i++)
			cin>>a[i];
		cout<<"最小值，方法一："<<searchMin(a,num)<<endl;
		
		cout<<"最小值，方法二："<<searchMin2(a,num)<<endl;
		delete[] a;	
	}
	return 0;
}
/*
8
1 2 3 4 5 6 7 8
8
5 6 7 8 1 2 3 4 
8
8 1 2 3 4 5 6 7 
8
2 3 4 5 6 7 8 1 
5
1 1 1 1 1
8
1 9 10 1 1 1 1 1
*/