# 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](https://leetcode.com/problems/search-in-rotated-sorted-array/description/), 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;
    }
}
```
