题目：
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.
Tag:
Array; Binary Search
体会：
这道题和Find the Minimum In Rotated Sorted Array肯定是有联系啦，毕竟给的都是Rotated Sorted Array这种结构。思路是：从middle处开始左右两部分，一部分是sorted的了，另一部分rotated或者sorted。我们要去分析sorted的那个部分。假设左边是sorted部分，如果A[left] <= target < A[mid]，那么target一定只可能出现在这个部分，otherwise，出现在另外一部分。如果右边是sorted，同理。
class Solution {
public:
int search (int A[], int n, int target) {
int low = ;
int high = n - ;
while (low <= high) {
int mid = low + (high - low) / ;
if (A[mid] == target) {
return mid;
}
if (A[mid] < A[high]) {
// right part is sorted, left is rotated part
if (A[mid] < target && target <= A[high]) {
// target must be in right part
low = mid + ;
} else {
// target must be left part
high = mid - ;
}
} else {
// left part is sorted
if (A[low] <= target && target < A[mid]) {
high = mid - ;
} else {
low = mid + ;
}
}
}
return -;
}
};