*Java* easy to understand iterative solution (0ms)


  • 0
    E

    The idea is very straightforward: First do a normal binary search and see if target is found.

    If target is not found, return. Otherwise, find the lower bound and upper bound. To save time, one trick is that when we try to find the lower and upper bounds, we only need to scan the portion with updated lo and updated hi, rather than 0 and nums.length-1. This is because after the first binary search, we already know that nums[lo]<=target and nums[hi]>=target.

    public int[] searchRange(int[] nums, int target) {
        int lo=0, hi=nums.length-1, mid=0;
        while(lo<=hi) {
            mid = lo + ((hi-lo)>>1);
            if(nums[mid]==target) break;
            else if(nums[mid]>target) hi = mid-1;
            else lo = mid+1;
        }
        
        if(lo>hi) return new int[]{-1,-1}; // never breaks the above while loop ==> target not found
        
        int leftHi = mid;
        while(lo<=leftHi) { // to locate lower bound for target
            int midLo = (lo+leftHi)>>1;
            if(nums[midLo]==target) leftHi = midLo-1;
            else lo = midLo+1;
        }   
        
        int rightLo = mid;
        while(rightLo<=hi) { // to locate upper bound for target
            int midHi = (rightLo+hi)>>1;
            if(nums[midHi]==target) rightLo = midHi+1;
            else hi = midHi-1;
        }
        
        return new int[]{lo, hi};
    }

Log in to reply
 

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