My concise O(logn) java solution


  • 0
    F
    public class Solution {
        public int[] searchRange(int[] nums, int target) {
            int index = binarySearch(nums,0, nums.length-1,target);
            if (index == -1){
                return new int[]{-1,-1};
            }
            int i = index+1;
            while(i<nums.length && nums[i] == target){
                i++;
            }
           return new int []{index,i-1};
        }
        
        private int binarySearch(int[]nums,int left,int right, int target){
            if (nums[left] == target){
                return left;
            }
            if (left >= right){
                return -1;
            }
            int mid = left + (right-left)/2;
            if(target<=nums[mid]){
               return binarySearch(nums,left,mid,target); 
            }else {
               return binarySearch(nums,mid+1,right,target); 
            }
        }
    }

  • 0

    The binary search is O(logn) that's great. But I think it is likely that the part

    while (i<nums.length && nums[i] == target){
            i++;
    }
    

    can be linear. Since there might be a lot(all) target in the array.

    Thanks.


  • 0
    I

    not exactlly O(N) for this part


Log in to reply
 

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