LeetCode C++ 81. Search in Rotated Sorted Array II【数组二分】中等

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2] ). You are given a target value to search. If found in the array return true , otherwise return false .

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3 Output: false

Follow up:

This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.Would this affect the run-time complexity? How and why?

题意：和33题差不多，假设按照升序排序的数组在预先未知的某个点上进行了旋转，我们需要判断给定的目标值是否存在于数组中。不同点在于，本题中的 nums 可能包含重复元素。

---

解法1 顺序查找

代码很简单：

class Solution { public: bool search(vector<int>& nums, int target) { for (int i = 0; i < nums.size(); ++i) if (nums[i] == target) return true; return false; } };

效率很奇特：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户 内存消耗：6.7 MB, 在所有 C++ 提交中击败了7.84% 的用户

---

解法2 二分

如果直接用33题的代码，毫无疑问会出现错误。因为数组 nums[] 中可能存在重复元素，比如 nums = [1,1,3,1], target = 3 ，第一次的二分 nums[mid] = nums[1] = 1 <= nums[hi] = 1 ，会错误判断 mid 落入数组右半部有序部分，然后比较 target > 1 得出 target 不存在于这一"有序部分"的错误结论，进而得到错误的结果。

因此，有必要慎重讨论二分法的细节：

每次二分，左半部分和右半部分至少有一边是有序的，分成两部分讨论；左半部分确定有序（nums[lo] < nums[mid]) ： ① target 落在左半边，对左半边继续二分；② 其他情况，排除左半边； 右半部分确定有序 (nums[mid] < nums[hi]) ： ① target 落在右半边，对右半边继续二分；② 其他情况，排除右半边； 处理重复情况。如果前面一个有序部分的情况都没判断出来，只能说明 nums[lo] = nums[hi] = nums[mid] 且不等于 target ，此时往中间压缩即可。

具体代码如下：

class Solution { public: bool search(vector<int>& nums, int target) { if (nums.empty()) return false; int lo = 0, hi = nums.size() - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] == target) return true; else if (nums[lo] < nums[mid]) { //[lo, mid)为有序部分 if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1; } else if (nums[mid] < nums[hi]) { //(mid,hi]为有序部分 if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1; } else { //nums[lo] == nums[hi] == nums[mid] != target while (lo <= hi && nums[lo] == nums[mid]) ++lo; while (lo <= hi && nums[hi] == nums[mid]) --hi; } } return false; } };

效率如下：

执行用时：4 ms, 在所有 C++ 提交中击败了96.99% 的用户 内存消耗：6.7 MB, 在所有 C++ 提交中击败了5.30% 的用户