81. Search in Rotated Sorted Array II

Leetcode link

解题思路

本题与 704 的 binary search其实本质上是相同的问题，只是这题在原来的基础上加了一个随机旋转数组的操作。但是我们仍然可以用二分的思想来做查找的动作，只是需要多判断一些条件

首先我们假设有这么一个数组 [1, 2, 3, 4, 5, 6, 7]，它经过旋转之后以最中间的数为观察点有 2 种情况：

• 左边升序、右边不一定升序，比如：[3, 4, 5, 6, 7， 1， 2]（以中间的数 6 来看，3～6 明显是升序的，6～2 明显不升序）

• 右边升序、左边不一定升序，比如：[6, 7, 1, 2, 3, 4, 5]（以中间的数 2 来看，6～2 明显不升序，2～5 明显升序）

但是题目说到数组允许重复数字，我们考虑到一种特殊的数组 [1, 1, 1, 1, 1, 2]，这种数组为我们的情况增加了一种：

• 左右两边都一定升序（只要数字 2 不刚好是中间数就会出现这种情况）

  
  

要使用二分法，需要确定三个点：left, right, mid

left 用来确定二分范围的左边界

right 用来确定二分范围的右边界

mid 是本次二分范围的中心，用来确定下一次二分的区域

本题我们只需要再针对上述三种状况分别判断一下就可以了：

1. 第一种情况，我们可以用 nums[mid] > nums[right] 为真来确定
2. 第二种情况，我们可以用 nums[mid] < nums[right] 为真来确定
3. 第三种情况，我们可以用 nums[mid] == nums[right] 为真来确定

用代码区分开了三种情况之后，我们只需要分别处理就好了，这里我们的思路可以概括为：柿子挑软的捏

1. 针对第一、第二种情况，我们只需要判断 target 是否在他们升序部分就好了，如果是就把范围定到升序部分之后处理就好（情况二刚好也可以处理升序）；如果不是就说明 target 要不在另一部分，要不不在数组中，我们把范围缩小到另一部分重新判断一次情况。
2. 针对第三种情况，我们只需要把 right - 1 就好了，也就是把右边范围缩小慢慢排除重复的数字

C++

class Solution {
 public:
  bool search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (nums[mid] == target) return true;
      // 确定是第一种情况
      if (nums[mid] > nums[right]) {
        // 如果它在升序的部分
        if (nums[mid] > target && nums[left] <= target) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
        // 确定是第二种情况
      } else if (nums[mid] < nums[right]) {
        // 如果它在升序的部分
        if (nums[mid] < target && nums[right] >= target) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
        // 确定是第三种情况
      } else {
        right--;
      }
    }
    // 找完之后没找到
    return false;
  }
};

Javascript

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (nums[mid] === target) return true;
      // 确定是第一种情况
      if (nums[mid] > nums[right]) {
        // 如果它在升序的部分
        if (nums[mid] > target && nums[left] <= target) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
        // 确定是第二种情况
      } else if (nums[mid] < nums[right]) {
        // 如果它在升序的部分
        if (nums[mid] < target && nums[right] >= target) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
        // 确定是第三种情况
      } else {
        right--;
      }
    }
    return false;
};