学步园

给定一个旋转了任意次的有序数组A和一个数n，实现一个O(logn)的算法返回n在A中的下标，若没有返回-1。（假定原有序数组是递增的）

例子：

输入：A：15,16,19,20,25,1,3,4,5,7,10,14；n：5

输出：8

思路：

有序数组旋转之后，前半部分仍是有序的，后半部分无序，仍然可以用二分的思想。

如果a[mid] == n，结束。

如果a[mid] > n，有两种情况：

1、如果a[mid] > a[left]，说明前半段有序：那么如果a[left] > n则n在后半段，否则在前半段；

2、如果a[mid] < a[left]，说明后半段有序：那么n在前半段。

如果a[mid] < n，情况类似。

该思路只适合没有重复数字的情况，如果有重复数字只有顺序查找了。

#include <iostream>
#include <vector>
using namespace std;

int Search(const vector<int>& v, int a)
{
	int l = 0, r = v.size() - 1;
	int m;
	while (l <= r)
	{
		m = l + ((r - l) >> 1);
		if (a == v[m])
			return m;
		else if (a < v[m])
		{
			if (v[l] < v[m])
			{
				if (a < v[l])
					l = m + 1;
				else
					r = m - 1;
			}
			else
				r = m - 1;
		}
		else if (a > v[m])
		{
			if (v[l] < v[m])
				l = m + 1;
			else
			{
				if (a < v[l])
					l = m + 1;
				else
					r = m - 1;
			}
		}
	}
	return -1;
}

int main()
{
	vector<int> v;
	int n;
	cin >> n;
	while (n--)
	{
		int m;
		cin >> m;
		v.push_back(m);
	}
	cin >> n;
	cout << Search(v, n) << endl;
    return 0;
}