Search in Rotated Sorted Array II

https://shuati.gitbook.io/crack-lintcode/~/edit/drafts/-LMEXK-ad6NF0h0R5L9C/binary-search/search-in-rotated-sorted-array-ii

只需要比之前的问题多考虑一个，就是左右中的数值相等的时候

判断左右中值之后的语句是else if，如果不是else if的话，最坏的情况下，他会继续往下判断。else if则会跳过后续判断，等到更新完mid值以后再判断

check nums[mid] < nums[start]的时候一定要加上等于。如果不加等于的话。。001120这个例子。start 和mid都 指到这两个1的时候。会调到else 语句，实际上不是，他们结果相同，在这里是可能出现的。所以=不能忘记

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;
            
            if(target == nums[mid])
                return true;
            
            if(nums[start] == nums[mid] && nums[mid] == nums[end]){
                end--;
                start++;
            }
            //等号不能省略
            else if(nums[mid] >= nums[start]){
                if(target >= nums[start] && target <= nums[mid]){
                    end = mid;
                }else{
                    start = mid;
                }
            }else{
                if(target >= nums[mid] && target <= nums[end]){
                    start = mid;
                }else{
                    end = mid;
                }
            }
        }
        
        if(nums[start] == target || nums[end] == target){
            return true;
        }
        
        return false;
    }
}