Share my java solution based on binary search


  • 0
    R

    The idea is basically find the first target location as mid, and then use the mid index as bound to search the left and right section. If there is no target exist in the left or right, simply return {mid, mid}, else if there is no target exist in the array, simply return {-1,-1}.

       public int[] searchRange(int[] A, int target) {
            int[] range = {-1,-1};
            if(A.length==0||A[A.length-1]<target||target<A[0]){
            	return range;
            }
            int mid = searchInsert(A, target, 0, A.length);
            if(mid!=-1){
            	range[0] = range[1] = mid;
            	int leftIndex = searchInsert(A, target, 0, mid-1);
            	while(leftIndex!=-1){
                	range[0] = leftIndex;
                	if(leftIndex==0) break;
            		leftIndex = searchInsert(A, target, 0, leftIndex-1);
            	}
            	int rightIndex = searchInsert(A, target, mid+1, A.length-1);
            	while(rightIndex!=-1){
                	range[1] = rightIndex;
                	if(rightIndex==A.length-1) break;
                	rightIndex = searchInsert(A, target, rightIndex+1, A.length-1);
            	}
            }
            return range;
        }
        public int searchInsert(int[] A, int target,int left, int right) {
            int mid = (left+right)/2;
            while(left<=right){
                if(A[mid] == target) return mid;
            	if(target<A[mid]){
            		right = mid-1;
            	} else {
            		left = mid+1;
            	}
        		mid = (left+right)/2;
            }
            return -1;
        }

Log in to reply
 

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