Self-explained Java Solution #binary-search


  • 2

    Simply use binary search to find the left bound and the right bound, if any.

    public class Solution {
        public int[] searchRange(int[] nums, int target) {
    
            int rl = _findBound(nums, target, true);
            int rr = _findBound(nums, target, false);
            return new int[]{rl, rr};
        }
        
        private int _findBound(int[] nums, int target, boolean leftBound) {
            
            int l = 0;
            int r = nums.length-1;
            
            while (l <= r) {
                int m = l + (r-l)/2;
                
                if (target < nums[m]) r = m-1;
                else if (target > nums[m]) l = m + 1;
                else {
                    if (leftBound) {
                        // return m if it's the left bound
                        if (m == 0 || nums[m-1] != target) return m;
                        else r = m-1;
                    } else {
                        // return m if it's the right bound
                        if (m == nums.length-1 || nums[m+1] != target) return m;
                        else l = m+1;
                    }
                }
            }
            return -1;
        }
    }
    

Log in to reply
 

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