81. Search in Rotated Sorted Array II

Leetcode Array Binary Search

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.

Your algorithm's runtime complexity must be in the order of $O(\log n$).

Example 1:

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

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. Search in Rotated Sorted Array最主要的区别是这里的数字是重复的。其实加上一个判断即可，即考虑特殊情况：nums[start] = nums[mid] = nums[end]。

public boolean search(int[] nums, int target) {
    if (nums == null || nums.length == 0) return false;
    int start = 0, end = nums.length - 1, mid, midVal;
    while (start <= end) {
        mid = (start + end) / 2;
        midVal = nums[mid];
        if (midVal == target) return true;
        //If we know for sure right side is sorted or left side is unsorted
        if (midVal > nums[start]) {
            if (midVal > target &&  target >= nums[start]) end = mid - 1;
            else start = mid + 1;
        //If we know for sure left side is sorted or right side is unsorted
        } else if (midVal < nums[start]) {
            if (midVal < target && target <= nums[end]) start =  mid + 1;
            else end = mid - 1;
        //If we get here, that means nums[start] = nums[mid] = nums[end], then shifting out
        //any of the two sides won't change the result but can help remove duplicate from
        //consideration, here we just use end-- but left++ works too
        } else {
            end--;
        }
    }
    return false;
}