Easy to understand recursive Java solution meets 86% of solution - No trick - Please leave feedback for improvement


  • 0
    C
    public static int[] searchRange(int[] nums, int target) {
            int lo;int hi = -1;
            //do regular binary search and spot where it occurs.
            int indexFirstSpotted = binarySearch(nums,0, nums.length-1,target);
            //now find the left most occurrence
            if(indexFirstSpotted > 0 && nums[indexFirstSpotted] == nums[indexFirstSpotted-1])
                lo = binarySearchLeft(nums,0,indexFirstSpotted-1, target);
            else
                lo = indexFirstSpotted;
            if(lo != -1){
                hi =  binarySearchRight(nums,indexFirstSpotted+1,nums.length-1, target);
            }
            return new int[]{lo,hi};
        }
    
        //now do regular recursive binary search
        public  static int binarySearch(int[] nums,int start, int end,int target) {
            if(start > end){
                return -1;
            }
            int mid = (start + end)/2;
            if(nums[mid] == target) {
                return mid;
            }
    
            if(target < nums[mid]){
                return binarySearch(nums,start, mid-1, target);
            }
            return binarySearch(nums,mid+1, end, target);
        }
    
    
        //Binary search for the left side
        public static int binarySearchLeft(int nums[], int start, int end, int target){
            if(start > end){
                return end+1;
            }
            int mid = (start + end)/2;
            if(nums[mid] == target){
                if(mid > 0 && nums[mid-1] == target){
                    int lowindex = binarySearchLeft(nums, start , mid-1,target);
                    if(lowindex != -1){
                        return lowindex;
                    }
                }
                return mid;
            }
    
            return binarySearchLeft(nums,mid+1, end, target );
        }
    
        //Binary search for the right side
        public static int binarySearchRight(int nums[], int start, int end, int target){
            if(start > end){
                return end;
            }
    
            int mid = (start + end)/2;
    
            if(nums[mid] == target){
                if(mid > 0 && mid < end && nums[mid+1] == target){
                    int hiIndex = binarySearchRight(nums,mid+1,end,target);
                    if(hiIndex != -1){
                        return hiIndex;
                    }
                }
                return mid;
            }
    
            return binarySearchRight(nums,start,mid-1,target);
        }
    

Log in to reply
 

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