原题地址

跟Find Minimum in Rotated Array类似，折半查找

将A平均分成两半A[l..m]和A[m+1..r]

如果target可能出现在A[l..m]，则保留A[l..m]，去掉A[m+1..r]

反之，保留A[m+1..r]，去掉A[l..m]。

根据区间的连续性判断target是否可能出现在其中，对于区间A[i..j]

如果A[i]<A[j]，说明A[i]到A[j]是递增的。target出现在其中的条件是A[i] <= target && target <= A[j]

如果A[i]>A[j]，说明A[i]到A[j]中间被折叠过。target出现在其中的条件是A[i] <= target || target <= A[j]

然后分别针对以上两种情况判断target是否可能出现在里面，如果可能，砍掉另一半，如果不可能，砍掉这一半，递归下去

注意n=0,1,2，m=l这些特殊情况

代码：

 1 int search(int A[], int n, int target) { 2   int l = 0; 3   int r = n - 1; 4  5   while (l <= r) { 6     int m = (l + r) / 2; 7     if (A[m] == target) 8       return m; 9     if ((A[l] < A[m] && (target >= A[l] && target < A[m]))10         || (A[l] > A[m] && (target >= A[l] || target < A[m])))11       r = m - 1;12     else13       l = m + 1;14   }15 16   return -1;17 }

Leetcode#33 Search in Rotated Sorted Array