1ms real O(log n) time complexity Java solution with explanation


  • -1

    I found that most of the shared code are not strictly O(log n) time complexity (at least when the worst case occurs, e.g. all elements in the array is target), here is my code that I think it will perform well at any cases:

    public int[] searchRange (int[] nums, int target) {
    	return searchRange(nums, 0, nums.length - 1, target);
    }
    
    private int[] searchRange (int[] nums, int from, int to, int target) {
    	if (from <= to) {
    		int mid = (from + to) / 2;
    		if (nums[mid] < target) // target is in the right part if exists
    			return searchRange(nums, mid + 1, to, target);
    		else if (nums[mid] > target) // target is in the left part if exists
    			return searchRange(nums, from, mid - 1, target);
    		// target appears in the middle of nums[from...to]
    
    		// search the left part recusively and pick out the lower index if exists
    		int left = searchRange(nums, from, mid - 1, target)[0];
    		left = left == -1 ? mid : left; // if target do not exist, then mid is the very left index
    
    		// search the right part recusively and pick out the higher index if exists
    		int right = searchRange(nums, mid + 1, to, target)[1];
    		right = right == -1 ? mid : right; // if target do not exist, then mid is the very right index
    
    		return new int[] { left, right };
    	}
    	return new int[] { -1, -1 };
    }

  • 0
    L

    It is really a right bullshit.


  • 0

    It would be highly appreciated if you could point out my fault instead just criticise


Log in to reply
 

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