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));
}
}
