Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

两层的二分查找，最外层的二分用来找到有序的部分，因为初始有序的数组被翻转后，其中的任何位置的元素都仍然属于一个有序的子序列，这个有序的子序列不是在左边有序，就是右边有序，当然也可能都有序。

里层的二分查找就简单了，就是我们所谓的二分查找，在一个有序的序列中查找给定值。

class Solution {
public:
	int search(int A[], int n, int target) {
		if(n == 0) return -1;
		int left = 0, right = n - 1;
		while (left <= right)
		{
			int midle = (left + right) >> 1;
			//右半部分有序
			if (A[midle] <= A[right])
			{
			    //右半部分包含目标值？
				if(A[midle] <= target && target <= A[right])
				{
				  int rlow = midle, rhigh = right;
				  while (rlow <= rhigh)
				  {
					  int mid = (rlow + rhigh) >> 1;
					  if(A[mid] == target) return mid;
					  else if(A[mid] < target) rlow = mid + 1;
					  else rhigh = mid - 1;
				  }
				}
				right = midle - 1;
			}
			//左半部分有序
			if(A[left] <= A[midle])
			{
			    //左半部分包含目标值？
				if (A[left] <= target && target <= A[midle])
				{
					int llow = left, lhigh = midle;
					while (llow <= lhigh)
					{
						int lmid = (llow + lhigh) >> 1;
						if(A[lmid] == target) return lmid;
						else if(A[lmid] < target) llow = lmid + 1;
						else lhigh = lmid - 1;
					}
				}
				left = midle + 1;
			}
		}
		return -1;
	}
};