Worse case O(logN) solution


  • -3
    Y

    I see some solutions used the binary search only once to find first occurrence of target, then search linearly to the left and right to get the range. This algorithm is fine but the worst case scenario the time complexity is O(N). Case: {3,3,3,3,3,3,........,3} target is 3.
    An improved version of above method is apply the binary search recursively until find the left most target and right most target. The worst case time complexity is also O(logN)
    Below is the code:

    public int[] searchRange(int[] nums, int target) {
        int[] range = {-1,-1};
        int begin=0, end=nums.length-1;
        int mid = binarySearch(nums, begin,end,target);
        if (mid==-1) return range;
        
        int index;
        while((index=binarySearch(nums, begin,end,target))!=-1){
        	range[0] = index;
        	end = index-1;
        }
        
        begin=0; end=nums.length-1;
        while((index=binarySearch(nums, begin,end,target))!=-1){
        	range[1] = index;
        	begin = index+1;
        }
              
        return range;
    }
    
    private int binarySearch(int[] nums, int begin, int end, int target){
    	int lo=begin, hi=end;
    	int mid=begin;
    	int index=-1;
    	while (lo<=hi){
    		mid = lo+(hi-lo)/2;
    		if(target<nums[mid]) hi = mid-1;
    		else if(target>nums[mid]) lo = mid+1;
    		else {
    			index = mid;
    			return index;
    		}
    	}
    	return index;
    }

Log in to reply
 

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