081. Search-in-Rotated-Sorted-Array-II

difficulty: Medium

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

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?

Method One

public class Solution {
​
    public boolean search(int[] nums, int target) {
        /**
        因为有 duplicates, 所以 worst case O(N);
        */
        int left = 0;
        int right = nums.length - 1;
        while( left <= right ) {
            int pivot = left + (right - left)/2;
            if (nums[ pivot ] == target) {
                return true;
            }
            //If we know for sure right side is sorted or left side is unsorted
            if (nums[pivot] < nums[right] || nums[pivot] < nums[left]) {
                if (target > nums[ pivot ] && target <= nums[ right ]) {
                    left = pivot + 1;
                } else {
                    right = pivot - 1;
                }
            //If we know for sure left side is sorted or right side is unsorted
            } else if (nums[ pivot ] > nums[ left ] || nums[ pivot ] > nums[right]) {
                if (target < nums[ pivot ] && target >= nums[ left ]) {
                    right = pivot - 1;
                } else {
                    left = pivot + 1;
                }
            //If we get here, that means nums[ left ] == nums[ pivot ] == nums[ right ], 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 {
                right--;
            }
        }

        return false;
    }
}
​
​

​