各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 73 天。今天力扣上的每日一题是「81. 搜索旋转排序数组 II」。

解题思路

一、搜索旋转无重复元素的排序数组

今天这个题目是第 33 题 搜索旋转排序数组 的变形。所以需要先弄懂 33 题。33 题是我经历过的面试题。

在有序的数组中，我们使用二分查找，可以根据 mid 的值去判断 left 或者 right 如何移动。其实这一步是二分查找的本质：减治法，就是说每次在二分搜索之后可以去除大概一半的元素可以不用再搜索，只在 target 所在的区间中继续搜索。二分查找的思想就是找出某个条件，这个条件给了我们移动左右指针的参考，即要判断查找的 target 在 mid 的左边还是右边。

具体到「搜索旋转无重复元素的排序数组」的题目，我们令 pivot 为旋转点的位置。那么：

  • 因为给出的数组是旋转有序的，如果 mid 指向的位置在于 pivot 之后，那么 mid 向后部分是有序的，这个时候需要判断 target 在 mid 左边还是右边，最简单的方法就是判断 target 是不是在 [pivot,r] 区间内，如果的话就向 mid 后半部分搜索，否则就向 mid 左半部分搜索；
    - 同理，当 mid 在 pivot 之前，那么 mid 前面部分是有序的，根据 target 判断下面要向 mid 的左边还是右边搜索。

下面的代码， nums[mid] <= nums[right] 就是判断 mid 点是不是在 pivot 之后。因为旋转数组是把大的数字旋转到了数组的前面，那么 nums[:pivot] 一定大于 nums[pivot:] ；所以如果 nums[mid] 比较小，那么它一定处于 nums[pivot:] 之中。

  1. class Solution(object):
  2.     def search(self, nums, target):
  3.         if not nums: return -1
  4.         left, right = 0, len(nums) - 1
  5.         while left <= right:
  6.             mid = (left + right) / 2
  7.             if nums[mid] == target:
  8.                 return mid
  9.             if nums[mid] <= nums[right]:
  10.                 if target > nums[mid] and target <= nums[right]:
  11.                     left = mid + 1
  12.                 else:
  13.                     right = mid - 1
  14.             else:
  15.                 if target < nums[mid] and target >= nums[left]:
  16.                     right = mid - 1
  17.                 else:
  18.                     left = mid + 1
  19.         return -1
  • 时间复杂度：$O(log(N))$
  • 空间复杂度：$O(1)$

二、搜索旋转有重复元素的排序数组

当搜索有重复元素的排序数组时，我们会遇到一个问题：如果 nums[left] nums[mid] nums[right] 时怎么办？比如 [2,1,2,2,2] 和 [2,2,2,1,2] ，最开始时，left 指向 第 0 位置，right 指向第 4 位置，mid 指向中间的 2 位置；此时三者相等都为 2。如果我们想找 1，而这个 1 可以在 mid 的左边也可以在 mid 的右边。所以就不知道该在哪个区间继续搜索。

一个解决本题的办法是，我们遇到 nums[left] == nums[right] 的情况时，直接向右移动 left，直至 nums[left] != nums[right]。那这样的话，上面的例子中就变成了在 [1,2,2,2] 和 [2,2,2,1] 上搜索，1 所在的区间就可以根据 mid 和 right 的大小关系而获得了。

代码如下，是在上面的代码的基础上增加了 nums[left] 和 nums[right] 相等的时候的判断代码。

  1. class Solution(object):
  2.     def search(self, nums, target):
  3.         if not nums: return -1
  4.         left, right = 0, len(nums) - 1
  5.         while left <= right:
  6.             mid = (left + right) / 2
  7.             if nums[mid] == target:
  8.                 return True
  9.             if nums[left] == nums[right]:
  10.                 left += 1
  11.                 continue
  12.             if nums[mid] <= nums[right]:
  13.                 if target > nums[mid] and target <= nums[right]:
  14.                     left = mid + 1
  15.                 else:
  16.                     right = mid - 1
  17.             else:
  18.                 if target < nums[mid] and target >= nums[left]:
  19.                     right = mid - 1
  20.                 else:
  21.                     left = mid + 1
  22.         return False
  • 时间复杂度：$O(log(N))$
  • 空间复杂度：$O(1)$

刷题心得

这个题目是二分搜索的常见改进，我在面试中也遇到了，大家需要掌握呀。

参考资料：
力扣官方题解
负雪明烛

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！