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 returntrue, otherwise returnfalse.

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, wherenumsmay contain duplicates.

• Would this affect the run-time complexity? How and why?

Analysis

这一题是Search in Rotated Sorted Array 的follow up，主要区别就是这里nums可能有重复元素。这样的话直接用原来的二分搜索就会有问题。这里需要注意的是如何处理重复元素。

同样是是先判断mid的左右区间是否为单调区间或者翻转区间，不同的是nums[mid]和nums[right]可能相等，这种情况下的处理就是移动搜索区间右边界right（因为是nums[mid], nums[right]比较，如果是nums[mid], nums[left]比较，则需要移动区间左边界left）。

有一个预处理搜索边界start/end的方法：

while (start < end && nums[start] == nums[start + 1])start++;
while (start < end && nums[end] == nums[end - 1]) end--;

Solution

Template #3 (compare nums[mid] vs nums[right]) - (1 ms, faster than 56.43%)

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        int left = 0, right = nums.length - 1;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return true;
            }
            if (nums[mid] < nums[right]) {
                // right part is sorted, left part is rotated 

                if (target > nums[right] || target < nums[mid]) {
                    // target is in rotated part
                    right = mid;
                } else {
                    left = mid;
                }

            } else if (nums[mid] > nums[right]) {
                // left part is sorted, right part is rotated 

                if (target < nums[left] || target > nums[mid]) {
                    // target is in rotated part
                    left = mid;
                } else {
                    right = mid;
                }
            } else {
                right--;
            }
        }
        if (nums[left] == target || nums[right] == target) {
            return true;
        }
        return false;
    }
}

@hpplayer Template #1 (compare nums[mid] vs nums[left]) - ()

public boolean search(int[] nums, int target) {
    int start  = 0, end = nums.length - 1;

    //check each num so we will check start == end
    //We always get a sorted part and a half part
    //we can check sorted part to decide where to go next
    while(start <= end){
        int mid = start + (end - start)/2;
        if(nums[mid] == target) return true;

        //if left part is sorted
        if(nums[start] < nums[mid]){
            if(target < nums[start] || target > nums[mid]){
                //target is in rotated part
                start = mid + 1;
            }else{
                end = mid - 1;
            }
        }else if(nums[start] > nums[mid]){
            //right part is rotated

            //target is in rotated part
            if(target < nums[mid] || target > nums[end]){
                end = mid -1;
            }else{
                start = mid + 1;
            }
        }else{
            //duplicates, we know nums[mid] != target, so nums[start] != target
            //based on current information, we can only move left pointer to skip one cell
            //thus in the worest case, we would have target: 2, and array like 11111111, then
            //the running time would be O(n)
            start ++;
        }
    }

    return false;
}

Template #1 with preprocessing of start, end

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