import java.util.Arrays;

class Solution {
    public boolean search(int[] nums, int target) {
        return search(nums, target, 0, nums.length-1);
    }
    private boolean search(int[] nums, int target, int l, int r){
        if( l <= r){
            // here we start as a regular binary search
            int mid = (r-l)/2 + l;
            //if target equals to mid/left/right, return true
            // to avoid collision (e.g. difference of target < nums and target <= nums)
            // we do it for l, mid, and r
            if(target == nums[mid] || target == nums[l] || target == nums[r]){
                return true;
            }
            //here is if there is a rotation in this array/subarray, we call it "twisted" 
            if(nums[r]>nums[l]){ // if nums[r] > nums[l], nums[l:r] is not a twisted array 
                if(nums[l] <= target && target <= nums[r]){ // if target in this array, do normal binary search
                    if(target == nums[mid]){
                        return true;
                    }else if(target < nums[mid]){ 
                        return search(nums, target, l, mid-1);
                    }else{
                        return search(nums, target, mid+1, r);
                    }
                }
            //here are cases for twisted array  
            }else if(nums[mid] == nums[l]){ // if mid and l are the same, we cannot know whether the left is twisted or the right is twisted
                                            // For example, [1,1,1,2,1] has a twisted array at right and [1,2,1,1,1] has a twisted array at left
                                            // But they all satisfy nums[mid] == nums[l]
                                            // Here we can only do O(n) search.
                return search(nums, target, l, mid-1)||search(nums, target, mid+1, r);
            }
            else if(nums[mid] > nums[l]){//if nums[mid] > nums[l], at least left subarray is not twisted array
                if(nums[l]<target && target<nums[mid]){ // if target is at left
                    return search(nums, target, l,mid-1);
                }else{  //else
                    return search(nums, target, mid+1,r);
                }
            }else{//if nums[mid] > nums[l], at least right subarray is not twisted array
                if(nums[mid] < target && target < nums[r]){//if target is at right
                    return search(nums, target, mid+1, r); 
                }else{//else
                    return search(nums, target, l, mid-1);
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1};
        System.out.println(new Solution().search(nums, 2));
    }
}