81. Search in Rotated Sorted Array II

image.png

class Solution {
    public boolean search(int[] nums, int target) {
        if(nums.length==0) return false;
        return helper(nums, 0, nums.length-1, target);
    }

    private boolean helper(int[] a, int lo, int hi, int target) {
        System.out.println(lo+" "+hi);
        if(lo>hi) return false;
        int mid = (lo+hi)/2;
        if(a[mid]==target) return true;
        
        if(a[mid]>a[lo]) {
            if(target>=a[lo] && target<=a[mid])
                return helper(a, lo, mid-1, target);
            else
                return helper(a, mid+1, hi, target);
        } else if(a[mid]<a[hi]) {
            if(target>=a[mid] && target<=a[hi])
                return helper(a, mid+1, hi, target);
            else
                return helper(a, lo, mid-1, target);
        } else {
            return helper(a, lo, mid-1, target) || helper(a, mid+1, hi, target);
        }
    }
    
    public static void main(String[] args) {
        Solution s=new Solution();
        System.out.println(s.search(new int[]{1,3}, 3));
    }
}