Share my Concise Java O(logN) solution, just 1 time Binary Search, easy to understand


  • 11
    S

    This solution is to find the start and end index of target number with using just one time binary search

    public int[] searchRange(int[] nums, int target) {
    		int[] res = {-1, -1};
    		int lo = 0, hi = nums.length - 1;
    
    		//lo is the start index of target
    		//hi is the end index of target
    		while(nums[lo] < nums[hi]) {
    			int mid = lo + (hi - lo)/2;
    			if(nums[mid] > target) {//target is in the left half
    				hi = mid - 1;
    			} else if(nums[mid] < target) {// target is in the right half
    				lo = mid + 1;
    			} else {//find target, then need to find the start and end point
    				if(nums[lo] == nums[mid]) {
    					hi--;
    				}else {
    					lo++;
    				}
    			}
    		}
    		//check whether find the target number
    		if(nums[lo] == nums[hi] && nums[lo]== target) {
    			res[0] = lo;
    			res[1] = hi;
    		}
    		
    		return res;
    	}

  • 1

    It seems that if all the elements in the array nums are target, your code won't satisfy the O(log n) time complexity, I mean your worst case is not O(log n).


  • 1
    S

    if all elements are target, it means nums[lo] == nums[hi] so the while loop would not run even for one time, so i think this should be one of best case instead of worse case


  • 1
    Y

    Well I think it's O(log n). Actually the trick here is the condition within while loop, it checks the value rather than the indices. It stops once the low value equals to high value. This is a good point.


  • 0
    Q

    there is a bug for while loop , for the case [5,6] 4, right will be -1.
    while(left < right && nums[left] < nums[right]){
    ....
    }


  • 0
    W

    E.g. if the first 501 elements in a 1001-element array are all target, the mid will point to the 501th element and satisfy "nums[lo] == nums[mid]". In that case, you will have 500 "hi--" operations (with nums[mid] always being target), which is O(n/2) => O(n), not O(lgN)


  • 0
    J

    I think it is still O(n), if middle half are the target number and first quarter and last quarter are not.


  • 0
    Q

    if lots of elements that equal to target are in the middle, the elements of both sides will be visited one by one. Consider if the array is somewhat like this: 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3, target is 2. we have n / 2 numbers that equal to target, it will run n - n / 2 = n / 2 time to get the result. It is not really O(logn)


  • 1
    R

    Your solution is elegant and efficient. I think it is O(n) as the condition within the while loop is "nums[lo] < nums[hi]". Therefore, no duplicate comparison will occur if there are duplicate matching numbers.


  • 1
    Z

    if there are many number of nums equal to target, it is O(n)


  • 0
    R

    elegant approach however it's o(n)
    thanks anyway


  • 2
    A

    @syjohnson No, it is O(n). Think about such testcase: an array of 1001 elements, only one element in the middle is the target. Then you literally have to go through n/2 iterations, which is O(n).


  • 0

    great solution!


  • 0
    R

    @yanxx It's not O(log n). Consider an array with the first and last elements are not equal to the target but rests are all targets, it's a linear time run.


  • 0
    M

    @robturtle It's a linear time array. But not in the case that you say. In the case that you mention, the while loop is run only twice.
    But, imagine the case where the target is the mid element in the array and all the other elements are different. It will increment the lo and and hi variables (n-1)/2 times each. So, it's linear.


  • 0
    P

    I think your code will fail on test case [1,2] given target is 0.


Log in to reply
 

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