Cacher is the code snippet organizer for pro developers

/*
一定是one side sorted another side unsorted

画图理解
必须要else{start++},相当于右移mid
之前的做法[1,3,1,1],3的case过不了
*/


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