原题链接

需要两次二分，第一次二分搜索旋转点的位置，第二次在旋转点的左侧或者右侧搜索目标值。二分不一定有序，但必须能找到一个性质将原问题分成两部分。本题中旋转点右侧的数小于数组第一个数，这个性质可以将原数组一分为二，因此可以二分找出旋转点。

需要注意的是，由于数组中有重复的数，需要将数组后半段中最后一段中所有和数组第一个数相等的数全部删掉才能保证：如果 nums[i] >= nums[0] 那么第 i 个数就在旋转点左侧这个性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  bool search(vector<int>& nums, int target) {
    if (nums.empty()) return false;
    int r2 = nums.size() - 1;
    while (r2 >= 0 && nums[r2] == nums[0]) r2--;
    if (r2 < 0) return nums[0] == target;
    int l = 0, r = r2;
    while (l < r) {
      int mid = l + r + 1 >> 1;
      if (nums[mid] >= nums[0]) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    int L, R;
    if (target < nums[0]) {
      L = l + 1;
      R = r2;
    } else {
      L = 0;
      R = l;
    }
    while (L < R) {
      int mid = L + R >> 1;
      if (nums[mid] >= target) {
        R = mid;
      } else {
        L = mid + 1;
      }
    }
    return nums[R] == target;
  }
};