# Intuitive Java Recursive Solution using Binary Search (avg, O(log(n)), worst case O(n))

• ``````public class Solution {

public boolean helper(int[] nums, int start, int end, int target) {
if(start>end)
return false;
int mid = start + (end - start) / 2;
if(nums[mid] == target)
return true;
if(nums[start] < nums[mid]) {
if(target >= nums[start] && target < nums[mid])
return helper(nums, start, mid-1, target);
else
return helper(nums, mid+1, end, target);
} else if(nums[start] > nums[mid]) {
if(target > nums[mid] && target <= nums[end])
return helper(nums, mid+1, end, target);
else
return helper(nums, start, mid-1, target);
} else {
if(nums[mid]==nums[end]) // in this case, the smaller or larger values (compare to nums[mid]) can be in either side
return helper(nums, start, mid-1, target) || helper(nums, mid+1, end, target);
else // this case we are sure that the left-side of mid are all duplicates
return helper(nums, mid+1, end, target);
}
}

public boolean search(int[] nums, int target) {
return helper(nums, 0, nums.length-1, target);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.