My accept Java solution using Binary Search. Wonder any good suggestion?


  • 2
    L

    Thank you for pointing out that my solution in fact takes O(n)

    The idea is that,

    1. First use Binary search to search a given target value.
    2. Then check its left side and right side, to see whether its duplicates exist.

    But I think my recursion function includes to many parameters, would this impact my performance? Could anyone give me some good advice about my solution to relieve this situation?

      public int[] searchRange(int[] A, int target) {
        int left = 0;
        int right = A.length - 1;
        int[] result = new int[2];
            
        _binarySearch(A, target, left, right, result);
        return result;
      }
      
      // recursive function
      public void _binarySearch(int [] A, int target, int left, int right, int[] result){
        // not exist
        if(left>right){
    
            result[0] = -1;
            result[1] = -1;
            return;
    
        }
        int mid = left + (right - left)/2;
        if(target == A[mid]){
            int start = mid;
            int end = mid;
            // check left side duplicates
            while(start > 0){
                if(A[start - 1] == target)
                    start--;
                else{
                    break;
                }    
            }
            // right side duplicates
            while(end < A.length - 1){
                if(A[end + 1] == target)
                    end++;
                else{
                    break;
                }    
            }
    
            result[0] = start;
            result[1] = end;
            
    
            
        }
        // on left side
        else if(target < A[mid]){
            _binarySearch(A, target, left, mid - 1, result);
        }
        // right side
        else if(target > A[mid]){
            _binarySearch(A, target, mid + 1, right, result);
        }
      }

  • 15
    Z

    suppose the input array is 2 2 2 2 .......(many 2s), for your algorithm, the run time will be O(n) which is the worst case, but not O(logn).

    when we find the target value A[mid] == target, we can continue using binary search to find the left or right bound, but before that, check whether it already reached the left/right bound (for left bound: if (mid == 0) or if (A[mid - 1] != target)).

    for the implementation, more lines needed as we find the target in the array, need to check A[i - 1] and A[i + 1], so define the methods separately. For the worst case, it is still O(logn)

    here is my solution:

    public class Solution {
        public int[] searchRange(int[] A, int target) {
            int[] arr = new int[2];
            arr[0] = searchLeft(A, target);
            arr[1] = searchRight(A, target);
            return arr;
        }
        
        private int searchLeft(int[] A, int target) {
            int s = 0, e = A.length - 1;
            while (s <= e) {
                int mid = s + (e - s) / 2;
                if (A[mid] == target) {
                    if (mid == 0) {
                        return mid;
                    }
                    if (A[mid - 1] == target) {
                        e = mid - 1;
                    } else {
                        return mid;
                    }
                } else if (target > A[mid]) {
                    s = mid + 1;
                } else {
                    e = mid - 1;
                }
            }
            return -1;
        }
        private int searchRight(int[] A, int target) {
            int s = 0, e = A.length - 1;
            while (s <= e) {
                int mid = s + (e - s) / 2;
                if (A[mid] == target) {
                    if (mid == A.length - 1) {
                        return mid;
                    }
                    if (A[mid + 1] == target) {
                        s = mid + 1;
                    } else {
                        return mid;
                    }
                } else if (target > A[mid]) {
                    s = mid + 1;
                } else {
                    e = mid - 1;
                }
            }
            return -1;
        }
    }
    

    the runtime is actually O(2*logn) as we need to search left & right separately


  • 0
    L

    Oh, really excellent solution!

    My solution only guarantee best case O(log(n))

    Thank you! Benefit a lot!


  • 0
    Z

    yeah, for the array without duplicate numbers, your sol will be O(logn).

    thanks!


  • 0
    S

    you don't need to define a global variable s,e,mid.yes?


  • 0
    L

    Yeah, I think so


  • 1
    L

    My solution uses a similar idea. A small modification is that I use binary search to check the left bound and right bound.

    public int[] searchRange(int[] A, int target) {
        if(A==null)
        	return new int[]{-1,-1};
        int l = 0,r = A.length-1,m;
        while(l<=r)
        {
        	m = (l+r)/2;
        	if(target<A[m])
        		r = m - 1;
        	else if(target>A[m])
        		l = m + 1;
        	else {
    			int mt = m, mm;
    			while(mt<r-1)
    			{
    				mm = (mt+r)/2;
    				if(A[mm]>target)
    					r = mm;
    				else 
    					mt = mm;						
    			}
    			if(A[r]>target)
    				r--;
    			mt = m;
    			while(l<mt-1)
    			{
    				mm = (l+mt)/2;
    				if(A[mm]<target)
    					l = mm;
    				else 
    					mt = mm;						
    			}
    			if(A[l]<target)
    				l++;
    			return new int[]{l,r};
    		}
        }
        return new int[]{-1,-1};
    }
    

  • 2
    Z

    My solution looks for left and right bounds using binary search. It is O(log(N)). I think it is very easy to understand.

    public class Solution {
        public int[] searchRange(int[] a, int target) {
            int l = searchRangeLeft(a, target);
            if(l == -1)
                return new int[] {-1, -1};
    
            int r = searchRangeRight(a, target);
    
            return new int[] {l, r};
        }
    
        private int searchRangeLeft(int[] a, int target) {
            int l = 0;
            int r = a.length-1;
            while (r-l > 1) {
                int m = l + (r-l)/2;
                if(a[m] < target) {
                    l = m;
                }
                else if(target <= a[m]) {
                    r = m;
                }
            }
    
            if(a[l] == target)
                return l;
            else if(a[r] == target)
                return r;
            else
                return -1;
        }
    
        private int searchRangeRight(int[] a, int target) {
            int l = 0;
            int r = a.length-1;
            while (r-l > 1) {
                int m = l + (r-l)/2;
                if(a[m] <= target) {
                    l = m;
                }
                else if(target < a[m]) {
                    r = m;
                }
            }
    
            if(a[r] == target)
                return r;
            else if(a[l] == target)
                return l;
            else
                return -1;
        }
    }

  • 1
    L

    My code, idea is same with others.

    public class Solution
    {
        private int searchLeft(final int[] A, final int target)
        {
            int left = 0;
            for (int right = A.length - 1; left <= right; )
            {
                final int middle = (left + right) / 2;
                if (A[middle] >= target)
                {
                    right = middle - 1;
                }
                else
                {
                    left = middle + 1;
                }
            }
            
            return (left >= A.length || A[left] != target) ? -1 : left;
        }
        
        private int searchRight(final int[] A, final int target)
        {
            int right = A.length - 1;
            for (int left = 0; left <= right; )
            {
                final int middle = (left + right) / 2;
                if (A[middle] <= target)
                {
                    left = middle + 1;
                }
                else
                {
                    right = middle - 1;
                }
            }
            
            return (right < 0 || A[right] != target) ? -1 : right;
        }
        public int[] searchRange(int[] A, int target)
        {
            final int[] result = new int[2];
            final int left = searchLeft(A, target);
            if (-1 == left)
            {
                result[0] = result[1] = -1;
            }
            else if (A.length - 1 == left)
            {
                result[0] = result[1] = left;
            }
            else
            {
                result[0] = left;
                result[1] = searchRight(A, target);
            }
            
            return result;
        }
    }

  • 0
    L

    Mine with similar idea.

    public class Solution {
        public int[] searchRange(int[] A, int target) {
            int[] result = new int[2];
            int start = 0;
            int end = A.length - 1;
            result[0] = result[1] = -1;
            while(start <= end && ((result[0] == -1) || (result[1] == -1))) {
                if(A[start] == target && result[0] == -1) {
                    result[0] = start;
                }
                if(A[end] == target && result[1] == -1) {
                    result[1] = end;
                }
                int middle = (start + end) / 2;
                if(A[middle] < target) {
                    start = middle + 1;
                }
                else if(A[middle] > target) {
                    end = middle - 1;
                }
                else {
                    if(result[0] == -1) {
                        start++;
                    }
                    if(result[1] == -1) {
                        end--;
                    }
                }
            }
            return result;
        }
    }

  • 1
    Z

    same idea, but when we know the left is not -1, we know the start for search right is left, at the same time, the right can not be return -1(it must be exist), the search for right can be simpler.

       public int[] searchRange(int[] A, int target) {
    
            if (A == null || A.length == 0) {
                return new int[] { -1, -1 };
            }
            int start = start(A, target);
            if (start == -1) {
                return new int[] { -1, -1 };
            }
    
            int end = end(A, start, A.length - 1, target);
            return new int[] { start, end };
        }
    
        private int start(int A[], int target) {
            int start = 0;
            int end = A.length - 1;
            while (start <= end) {
                if (start == end && A[start] == target) {
                    return start;
                }
    
                int mid = (start + end) / 2;
                if (A[mid] > target) {
                    end = mid - 1;
                    continue;
                }
                if (A[mid] < target) {
                    start = mid + 1;
                    continue;
                }
                end = mid;
            }
    
            return -1;
        }
    
        private int end(int A[], int start, int end, int target) {
            while (true) {
                if (start == end) {
                    return start;
                }
                int mid = (start + end + 1) / 2;
                if (A[mid] > target) {
                    end = mid - 1;
                    continue;
                }
                start = mid;
            }
        }

  • 0
    W
    public int[] searchRange(int[] A, int target) {
    	int i = 0, j = A.length-1;
    	int left = -1, right = -1;
    	int mid = 0;
    	//judge if the target exists or not
    	while(i <= j){
    		mid = i + ((j-i)>>1);
    		if(A[mid] == target)
    			break;
    		else if(A[mid]>target)
    			j = mid - 1;
    		else i = mid + 1;		
    	}
    	//if target is not in the array
    		if(A[mid] != target)	return new int[]{-1,-1};
    		//search the left indice
    		i = 0;j = mid -1;
    		while(i <= j){
    			mid = i + ((j-i)>>1);
    		if(A[mid] == target)
    			j = mid - 1;
    		else i = mid + 1;		 	
    		}
    		left = i;
    		//find the right indice
    		i = mid+1;j = A.length -1;
    		while(i <= j){
    			mid = i + ((j-i)>>1);
    		if(A[mid] == target)
    			i = mid + 1;
    		else j = mid - 1;		 	
    		}
    		right = j;
    	return new int[]{left,right};    
    }

  • 0
    A

    There's no need for two versions of binary search: for right bound just search for [target+1] and shift one position to the left.

    public class Solution {
        public int[] searchRange(int[] nums, int target) {
            
            // 1. Search for the left bound
            int left = binarySearch(nums, target);
            
            // 2. No target found -- return
            if (left >= nums.length || nums[left] != target)
                return new int[] {-1, -1};
    
            // 3. Search for the right bound
            int right = binarySearch(nums, target + 1) - 1;
            return new int[] { left, right };
        }
    
        /* Returns index of first target if found or 
           index of the first element larger than target */    
        private int binarySearch(int[] nums, int target) {
            int lo = 0;
            int hi = nums.length - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (nums[mid] < target)
                    lo = mid + 1;
                else 
                    hi = mid - 1;
            }
            return lo;
        }
    }

  • 0

    Please see my explanation here


  • 0
    L

    this is my solution, i thing it takes O(logn) times too but more than 2 * logn.

    var searchRange = function(nums, target) {
     
       var result = [-1, -1];
       var binarysearch = function findTarget(A, l, h, target) {
    
    	if (l > h) {
    		return -1;
    	}
    	var mid =(h + l)/2;
    	var mid =  Math.floor(mid)
    	if (A[mid] === target) {
    		return mid;
    	}
    	if (target < A[mid]) {
    		return findTarget(A, l , mid-1, target);
    	}else {
    		return findTarget(A, mid+1, h, target);
    	}
    }
    
    var res = binarysearch(nums, 0, nums.length - 1, target);
    console.log(res);
    if (res === -1) {
    	return [-1, -1];
    }else {
    	var left = res;
    	var right = res;
    	while (left > -1) {
    		result[0] = left;
    		left = binarysearch(nums, 0, left - 1, target);
    	}
    	while (right > -1) {    		
    		result[1] = right;
    		right = binarysearch(nums, right + 1, nums.length - 1 , target);
    	}
    	return result;
    }
    

    };`


Log in to reply
 

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