Easy-to-understand solution by using 2 times BS to get lower and upper bounds separately (Java)


  • 0
    public class Solution {
        public int[] searchRange(int[] nums, int target) {
            
            int l = 0;
            int r = nums.length - 1;
            int i1 = -1;
            int i2 = -1;
            
            while (l<=r) {
                
                int mid = (l+r)/2;
                
                if (nums[mid]>target) {
                    r = mid-1;
                } else if (target>nums[mid]) {
                    l = mid+1;
                } else {
                    if(i1==-1) {
                        i1 = mid;
                    } else if (mid<i1) {
                        i1 = mid;
                    }
                    r = mid-1;
                }
                
            }
            
            l = 0;
            r = nums.length - 1;
            
            while (l<=r) {
                
                int mid = (l+r)/2;
                
                if (nums[mid]>target) {
                    r = mid-1;
                } else if (target>nums[mid]) {
                    l = mid+1;
                } else {
                    if(i2==-1) {
                        i2 = mid;
                    } else if (mid>i1) {
                        i2 = mid;
                    }
                    l = mid+1;
                }
                
            }
            
            return new int[]{i1, i2};
            
        }
    }
    

Log in to reply
 

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