LeetCode 81. Search in Rotated Sorted Array II

[Woodyiiiiiii]

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?

---

这道题是第I类型的变种，在第I题中，因为元素不重复，满足中间元素小于最右元素则右边有序，中间元素大于最右元素则左边有序。这题因为可能会出现中间元素等于最右元素的情况，这时候只需要减小右边界，变化最右元素，使这种情况不出现。

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] < nums[right]) {
                if (nums[mid] < target && nums[right] >= target) {
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }else if (nums[mid] > nums[right]) {
                if (nums[left] <= target && nums[mid] > target) {
                    right = mid - 1;
                }
                else {
                    left = mid + 1;
                }
            }else {
                --right;
            }
        }
        return false;
    }
}

---

参考资料：

• https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
• [LeetCode] 81. Search in Rotated Sorted Array II grandyang/leetcode#81