A very simple Java solution, with only one binary search algorithm


  • 125
    K
    public class Solution {
    	public int[] searchRange(int[] A, int target) {
    		int start = Solution.firstGreaterEqual(A, target);
    		if (start == A.length || A[start] != target) {
    			return new int[]{-1, -1};
    		}
    		return new int[]{start, Solution.firstGreaterEqual(A, target + 1) - 1};
    	}
    
    	//find the first number that is greater than or equal to target.
    	//could return A.length if target is greater than A[A.length-1].
    	//actually this is the same as lower_bound in C++ STL.
    	private static int firstGreaterEqual(int[] A, int target) {
    		int low = 0, high = A.length;
    		while (low < high) {
    			int mid = low + ((high - low) >> 1);
    			//low <= mid < high
    			if (A[mid] < target) {
    				low = mid + 1;
    			} else {
    				//should not be mid-1 when A[mid]==target.
    				//could be mid even if A[mid]>target because mid<high.
    				high = mid;
    			}
    		}
    		return low;
    	}
    }

  • 5
    L

    basically it is the same idea with using separate binary search for left and right bounds.
    The good point here is the lower_bound and the search for (target+1)


  • 1
    S

    Brilliant solution


  • -4
    M

    One Pass O(logn) Binary Search Solution No Helper, based on your idea with some improvement.

    public int[] searchRange(int[] nums, int target) {
            int min = -1;
            int max = -1;
            int[] ret = {-1,-1};
            
            int l = 0;
            int r = nums.length -1;
            int mid = (l + r) /2;
            
            if(l > r)//where left surpass right, which means no elements left in the array
            return ret;
            
            if(nums[mid] == target){//once target is hit, search its left sub array, and right right sub array to find the left most target, and right most target
                min = mid;
                max = mid;
                
                int[] newleft =  Arrays.copyOfRange(nums, 0, mid);//inclusive, exclusive
                int[] newright =  Arrays.copyOfRange(nums, mid + 1, nums.length);
                
                ret = searchRange(newleft,target);
                if(ret[0] != -1) min = ret[0];//update min if target is hit in the left sub array
                ret = searchRange(newright,target);
                if(ret[1] != -1) max = mid + 1 + ret[1];// update max if the target is hit, meanwhile adjust index to the original array
                
                return new int[]{min,max};
            }else if(nums[mid] > target){ // search left 
                int[] newleft =  Arrays.copyOfRange(nums, 0, mid);//inclusive, exclusive
                return searchRange(newleft,target);
            }else if(nums[mid] < target){// search right
                int[] newright =  Arrays.copyOfRange(nums, mid + 1, nums.length);
                ret = searchRange(newright,target);
                if(ret[1] != -1){//adjust left most right index to the original array
                    ret[1] = ret[1] + mid + 1;    
                }
                 if(ret[0] != -1){
                    ret[0] = ret[0] + mid + 1;    //adjust left most target index to the original array
                }
                return ret;
            }
            
            return ret;
        }

  • -3

  • 2
    E

    Well, to be frank, I don't see an improvement in your code. It is actually even slower than the original one because you are copying the array several times, which is time consuming. To be precise, your algorithm is of time O(n) rather than O(log n) because copying an array is of O(n).


  • 0
    L

    really nice solution! but i don't see the reason why you used " int mid = low + ((high - low) >> 1);". I tried mid = (high+low)/2 and it also worked.


  • 0
    M

    Hello @lhai, this is a trick of preventing possible overflow. Imagine a case where low = Integer.MAX_VALUE - 10, high = Integer.MAX_VALUE - 5


  • 8
    R

    But I think (target + 1) may caused overflow...


  • 0
    J

    @kxcf
    I always wonder when we set high equal to A.length or A.length-1. Could anyone please provide some explanation? Thank you!


  • 0
    D

    Slight optimization, if you pass in high and low into the helper method as parameters then at line 7 you can pass in start as the new low. Would save you log(n) iterations in the helper for the worse case of target being all the way to the right.

    target = 10
    [1,1,1,1,1,1,1,1,1...................a lot of 1's...................10,11]


  • 0
    L

    you are so clever!!! my method is similar to yours, but i use two extra methods and have wrote some silly codes. 0.0


  • 0
    R

    @jun711
    Yes, I was wondering about the same question: high = A.length vs high = A.length-1


  • 2
    H

    @jun711

    I think it's for the case in which there is only one element.
    For example, in the test case: [1] 1
    If you use high = A.length - 1;
    high will be 0 (1-1)
    This makes while (low < high) false.
    So every time you call firstGreaterEqual(), it will return 0 directly.
    Thus, return new int[]{start, Solution.firstGreaterEqual(A, target + 1) - 1};
    will return {0, -1}, which is incorrect.


  • 0
    T

    @kxcf what will happen if the number just bigger than target doesn't equal target+2,


  • 0
    C

    @kxcf If target+1 is not in the array, then the right end of the range should be firstGreaterEqual(A, target + 1). Is this right?


  • 0
    C

    @cutezgh said in A very simple Java solution, with only one binary search algorithm:

    @kxcf If target+1 is not in the array, then the right end of the range should be firstGreaterEqual(A, target + 1). Is this right?

    Never mind. Your firstGreaterEqual finds the left end of the range if the target exists, and the first number greater than the target if it doesn't exist. Basically, high = n (not n-1) is important.


  • 0
    Y

    My python solution is similar :)

    class Solution(object):
        def searchRange(self, nums, target):
            def BinSearch(arr,x):
                l=0
                r=len(arr)-1
                while l<=r:
                    mid=(l+r)/2
                    if arr[mid]<x:
                        l=mid+1
                    else:
                        r=mid-1
                return l
         
            if not nums: return [-1,-1]
            start=BinSearch(nums,target)
            end=BinSearch(nums,target+1)-1
            if start<=end:
                return [start,end]
            else:
                return [-1,-1]
    #87 / 87 test cases passed.
    #Status: Accepted
    #Runtime: 38 ms
    

  • 0
    P

    @kxcf

    public class Solution {
    public int[] searchRange(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length -1;
    int rh = -1;
    int rl = -1;

        while(lo<=hi){
            int mid = (lo+hi)/2;
            if(target == nums[mid]){
                rl = focc(lo,mid,target,nums);
                rh = locc(mid,hi,target,nums);
                break;
            }
            else if(target<nums[mid])
                hi = mid-1;
            else
                lo = mid+1;
        }
        int[] a = new int[2];
        a[0] = rl;
        a[1] = rh;
        return a;
    }
    int focc(int lo,int hi,int t,int[] n){
        while(lo<=hi){
            int m = (lo+hi)/2;
            if(t==n[m]){
                if(m==lo || n[m-1]<t)
                    return m;
                else
                   hi = m-1; 
            }
            else
                lo = m+1;
        }
        return -1;
    }
    int locc(int lo,int hi,int t,int[] n){
        while(lo<=hi){
            int m = (lo+hi)/2;
            if(t==n[m]){
                if(m==hi || n[m+1]>t)
                    return m;
                else
                   lo = m+1; 
            }
            else
                hi = m-1;
        }
        return -1;
    }
    

    }

    This is my solution.. can someone help me figure out its complexity and is it more time consuming than the one posted?


  • 1
    T

    @kxcf great! Thanks for sharing!!!

    public class Solution {
        public int[] searchRange(int[] nums, int target) {
            if(nums==null || nums.length<1){
                return new int[]{-1,-1};
            }
            
            int start=searchBinary(nums,target);
            if(start==nums.length || nums[start]!=target){
                return new int[]{-1,-1};
            }
            
            int end = searchBinary(nums,target+1);
            return new int[]{start,end-1};
        }
        
        public int searchBinary(int[] nums,int target){
            int i=0;
            int j=nums.length;
            while(i<j){
                int mid=(i+j)>>>1;
                if(nums[mid]<target){
                    i=mid+1;
                }else{
                    j=mid;
                }
            }
            
            return i;
        }
    }
    
    

Log in to reply
 

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