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


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

Log in to reply
 

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