题目：
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.
思路： 不同于普通的B search， 此题需要判断左右哪一部分是正常没有折叠过的 （有且只有一边没有折叠）。
代码：
class Solution { public: int search(int A[], int N, int key) { int L = 0; int R = N - 1; while (L <= R) { // Avoid overflow, same as M=(L+R)/2 int M = L + ((R - L) / 2); if (A[M] == key) return M; // the bottom half is sorted if (A[L] <= A[M]) { if (A[L] <= key && key < A[M]) R = M - 1; else L = M + 1; } // the upper half is sorted else { if (A[M] < key && key <= A[R]) L = M + 1; else R = M - 1; } } return -1; } };
转载于:https://www.cnblogs.com/tanghulu321/archive/2013/05/02/3054395.html
