81. Search in Rotated Sorted Array II

Problem:

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

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

Analysis:
6/19/2018 update:
If only compares with left, we can only increment left when there is duplicate.

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 <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return true;
            else if (nums[mid] > nums[left]) {
                if (target < nums[mid] && target >= nums[left])
                    right = mid - 1; 
                else left = mid + 1;
            } else if (nums[mid] < nums[left]){
                if (target > nums[mid] && target <= nums[right])
                    left = mid + 1;
                else 
                    right = mid - 1;
            } else {
                left++;
            }
        }    
        return false;
    }
}

_________________________________________________________________________________
因为二分法需要在一个单调区间执行，所以要去重复。
nums[mid] == nums[start]:start++
nums[mid] == nums[end]: end--;
其他处理和上一个问题一样

Solution:

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+ 1< end) {  
            int mid = start+ (end- start)/2;  
            // mid is on left
            if (nums[mid] == target) return true;
            else if (nums[mid] > nums[start]){  
                if (nums[mid] > target && target >= nums[start] ) end = mid;
                else start = mid;
            }  else if (nums[mid] < nums[end]){
                if (nums[mid] < target &&  target <= nums[end]) start = mid;
                else end = mid;
            } else if (nums[mid] == nums[start]) start++;
            else {
                end--;
            }
        }
        if (nums[start] == target) return true;
        else  if (nums[end] == target) return true;
        else return false;
    }
}