My Recursive solution in Java.


  • 0
    G

    I have used recursive approach.Below is my code. Explanation is in the comments.
    Basic Intuition was

    1. We need to discard left/right portion of array if mid is not equal to target
    2. If mid is equal to target, then we call binarySearch for both left and right parts of array and merge into the result.
      Would be glad if anyone has feedback for me.
     public int[] searchRange(int[] nums, int target) {
            
            int[] result = {-1,-1};
            if(nums==null || nums.length==0){
                return result;
            }
            
            result = binarySearch(nums,target,0,nums.length-1);
            
            return result;
        }
        
        public int[] binarySearch(int[] nums,int target, int low, int high)
        {
            
            int[] result = {-1,-1};
            if(high<low){
                return result;
            }
            
            if(nums[low]==nums[high] && nums[low]==target){ // if entire range is equal to target
                result[0]=low;
                result[1]=high;
                return result;
            }
            
            int mid = low + (high-low)/2;
            
            if(nums[mid]>target){           // if middle element is greater than target, search in left portion
                return binarySearch(nums,target,low,mid-1);
            }else if(nums[mid]<target){         // if middle element is less than target search in right portion
                return binarySearch(nums,target,mid+1,high);
            }
            else{       // if mid is equal to target, call two binary search with low..mid and mid..high and merge
                int[] temp1 = binarySearch(nums,target,low,mid);
                int[] temp2 = binarySearch(nums,target,mid+1,high);
                // merge the two results;
                result[0]=temp1[0]!=-1?temp1[0]:temp2[0];       // check if it is in left portion
                result[1]=temp2[1]!=-1?temp2[1]:temp1[1];
                return result;
            }
            
        }
    

Log in to reply
 

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