又是恶心的折半查找题。
题目中说这道题是根据 Search in Rotated Sorted Array 的扩展，可是我竟根本没遇到过这一道题，查了下，还在后面。所以比较尴尬，这也许就是按照通过率做题的弊端吧。
但还好，我做过一个类似的，那道题是求最小值，难度还要再大一些呢。
正好是接受那道题的教训，这次我好好的画了三张图：
可以看到，1是没经过旋转的，所以基本保持了有序状态；2和3都旋转了，只不过中点一个是最大值，一个是最小值。（mid我用红圈，首尾用的黑圈）
咱们的折半一定要将这三种情况想全面。
首先，如果要让 right = mid-1，即将范围缩小到左子数组，需要什么条件？
- 对于图1，要 A[l] < target < A[m]
- 对于图2和图3，只要 target > A[l]
如何区分这两种情况？
- 对于图1和图2，A[l] < A[m]
- 对于图3，A[l] > A[m]
有人说为啥不考虑相等的情况，答曰：太复杂，理不清，不如一开始就将相等的情况剔除：
// 最开始
if (target == A[m] || target == A[l] || target == A[r]) return ture;
// 最后面
++l, ++r这样就剔除了相等情况下的干扰。
若要将范围缩小到右子数组，就着眼于 A[r] 即可，思路与上面类似。不赘述了。
class Solution {
public:
bool search(int A[], int n, int target) {
if (n<0) return false;
for (int l=0, r=n-1; l<=r; )
{
int m = (l+r) >> 1;
if (target == A[m] || target == A[l] || target == A[r]) return true;
else if ((A[l] < A[m] && target > A[l] && target < A[m]) || (A[l] > A[m] && target > A[l])) r = m-1;
else if ((A[m] < A[r] && target > A[m] && target < A[r]) || (A[m] > A[r] && target < A[r])) l = m+1;
else ++l, --r;
}
return false;
}
};