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?

Solution

class Solution {
    public boolean search(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while(hi >= lo){
            int mid = lo + (hi-lo)/2;
            if(nums[mid] == target) return true;
            //the right side is sorted or left side is unsorted
            if(nums[mid] < nums[hi]  || nums[mid] < nums[lo]){ 
                
                //check if target is belong to the right side
                if(nums[mid] < target && nums[hi] >= target ){
                    lo = mid+1;
                }
                else{
                    //shall belong to left side
                    hi = mid-1;
                }
            }
            //the left side is sorted or right side is unsorted
            else if(nums[mid] > nums[lo]  || nums[mid] > nums[hi]){ 
                //check if the target is belong to the left side
                if(target < nums[mid] && target >= nums[lo]){
                    hi = mid - 1;
                }
                else{
                    //shall belong to right side 
                    lo = mid + 1;
                }
            }
            else{
                //which means the both side is unsorted, ie lo = mid = hi
                lo++;
            }
            
        }
        return false;
    }
}