[セットトップ]回転配列の最小値

题目:1つの配列の最も开いたいくつかの要素を配列の末尾に运んで、私达は配列の回転と称して、1つの増加して顺位する配列の1つの回転を入力して、回転する配列の最小要素を出力して、例えば:配列{3,4,5,1,2}が回転した后に{1,2,3,4,5}で、この配列の最小値は:1です
解析:
これは最近剣指offerを見て、それからこの問題を見て、それから上の解法は2種類あります:1、最も考えやすい1種で、配列を昇順に並べて、それから配列の最初の数は最小値で、しかしその時間の複雑度は最も良くてもO(logn)でなければなりません、(速く並べて、まとめて、積み上げて並べ替えます).2、このような二分検索の思想に基づいて、1つの局部秩序の配列でも二分検索を使うことができますが、剣指offerが書いたコードは最初は{1,1,0,1,1}という状況を考慮していませんでした.後でこのような状況のプログラムを考えて書いたとしても、個人的には彼が書いたコードは少し簡潔ではないと思います.もしあなたが私と同じ考えを持っているならば、それからあなたは私のコードを見て意味があって、すべて注釈があって、ここでは多く言わないで、直接コードに行きます

#include <iostream>
#include <assert.h>
using namespace std;

//        
//3,4,5,6,7,1,2--->  1
//6,7,1,2,3,4,5--->  1
//[]   
int min_key(int *arr,int low,int heigh)
{
	int begin=arr[low];
	int end=arr[heigh];
	while(low <= heigh)
	{
		int mid=low+(heigh-low)/2;
		//1,1,1,1,0,0
		if(arr[low] <= arr[mid] && arr[low] >= arr[heigh])//             
		{
			low=mid;
			if(heigh-low == 1)
				return arr[heigh] <arr[low] ? arr[heigh]:arr[low];
		}//             ，             
		else if(arr[low] < arr[mid] && arr[low] < arr[heigh])
			return arr[low];
		//             ，             
		else if(arr[low] > arr[mid] && arr[mid] > arr[heigh])
			return arr[heigh];
		//             
		else if(arr[low] >= arr[mid] && arr[mid] <= arr[heigh])
		{
			heigh=mid;
			if(heigh-low == 1)
				return arr[heigh] <arr[low] ? arr[heigh]:arr[low];
		}
	}
	return -1;
}
int min_value(int *arr,int len)
{
	assert(arr !=NULL);
	return min_key(arr,0,len-1);
}

int main()
{
	//int arr[]={3,4,5,6,7,1,2};
	//int arr[]={1,2,3,4,5,6,7};
	//int arr[]={7,6,5,4,3,2};
	//int arr[]={6,7,1,2,3,4};
	//int arr[]={1,1,1,1,0,0};
	//int arr[]={0,1,1,1,0,0};
	int arr[]={1,1,0,1,1,1};
	int len=sizeof(arr)/sizeof(*arr);
	int min=min_value(arr,len);
	cout<<"min is :"<<min<<endl;
	return 0;
}