Fairly concise O(lg n) recursive Java solution


  • 0
    A

    Used a modified binary search that can find the index of either the leftmost edge or rightmost edge of a section with equal values.

    public class Solution 
    {
        public int[] searchRange(int[] nums, int target) 
        {
            int leftIndex = edgeBinarySearch(nums, target, 0, nums.length - 1, true);
            int rightIndex = edgeBinarySearch(nums, target, 0, nums.length - 1, false);
            int[] range = {leftIndex, rightIndex};
            return range;
        }
        
        public int edgeBinarySearch(int[] nums, int target, int low, int high, boolean leftEdge)
        {
            if(low > high)
            {
                return -1;
            }
            int mid = (low + high)/2;
            boolean equals = (nums[mid] == target);
            if(equals)
            {
                boolean prevDifferent = (mid == 0) || nums[mid - 1] != target;
                boolean nextDifferent = (mid == nums.length - 1) || nums[mid + 1] != target;
                if((leftEdge && prevDifferent ) || (!leftEdge && nextDifferent ))
                {
                    return mid;
                }
            }
            if(nums[mid] > target || (equals && leftEdge))
            {
                return edgeBinarySearch(nums, target, low, mid - 1, leftEdge);
            }
            return edgeBinarySearch(nums, target, mid + 1, high, leftEdge);
        }
    }
    

Log in to reply
 

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