マイクロポリシー面接問題:回転後の配列で要素を検索(二分検索)

著作権所有.権利留保
転載を歓迎します.転載する時は出所を明記してください.
http://blog.csdn.net/xiaofei_it/article/details/17123303
繰り返し要素のない秩序配列で、数回回転した後、新しい配列が得られます.例えば[1,4,5,8,10,12,56,78]は[12,56,78,1,4,5,8,10]になる.
この配列で要素を探します.
実はアルゴリズムは簡単で、二分で検索するのですが、midがどの部分(前半か後半か)に属しているかを見るだけなので、4つのケースがあります.
コードは以下の通りです

#include <iostream>

using namespace std;

int a[1000];

int find(int a[],int len,int x)

{

	int start=0,end=len-1,mid;

	while (start<=end)

	{

		mid=(start+end)/2;

		if (a[mid]==x)

			return mid;

		if (a[start]<a[mid])

		{

			if (a[mid]<x)

				start=mid+1;

			else

				end=mid-1;

		}

		else

		{

			if (a[mid]<x)

				end=mid-1;

			else

				start=mid+1;

		}

	}

	return -1;

}

int main()

{

	int n,x;

	while (cin>>n>>x)

	{

		for (int i=0;i<n;i++)

			cin>>a[i];

		cout<<find(a,n,x)<<endl;

	}

	return 0;

}

 
 
以上のコードによる入出力の処理はACMを模したものである.nは配列要素の個数を表し、xは探している要素を表し、n個の数(重複がなく、回転後の配列であることを保証します).
また、なぜ重複がないのかを話します.繰り返しがあればmidでどの部分に属するか判断できず、他の方法で調べるのは簡単な二分検索ではなく、時間の複雑さもO(log n)ではありません.
たとえば
3,3,3,3,5,3,3,3,3中探し5
3,3,3,3,3,3,3,5,3中探し5
3,3,3,3,1,3,3,3,3の中で1を探します
3,3,3,3,3,3,3,1,3の中で1を探します