Simple recursive Java solution, O(logn)


  • 0
    Y

    Modified from binary search. Keeps updating the index of range.

    public class Solution {
        public int[] searchRange(int[] A, int target) {
            int[] ans = new int[]{-1,-1};
            searchRange(A, target, 0, A.length-1, ans);
            return ans;
        }
        
        private void searchRange(int[] A,  int target, int start, int end, int[] ans){
            if(end<start) return;
            int l =start, r = end, mid;
            while(l<=r){
                mid = l+(r-l)/2;
                if(A[mid]==target){
                    ans[0] = (ans[0]>=0)? Math.min(ans[0],mid):mid;
                    ans[1] = Math.max(ans[1],mid);
                    searchRange(A,target,l,mid-1,ans);
                    searchRange(A,target,mid+1,r,ans);
                    return;
                }
                else if(A[mid]>target) r = mid-1;
                else l = mid+1;   
            }
            return;          
        }
    }

Log in to reply
 

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