C# log(n)+k k is the length of the result


  • 0
    Y
    public class Solution {
        public int[] SearchRange(int[] nums, int target) {
            //binary search
            int n=nums.Length;
            if(n==0)
                return new int[2]{-1,-1};
            int left=0,right=n-1;
            while(left<=right)
            {
                int mid=left+(right-left)/2;
                if(nums[mid]==target)
                    return findRange(nums,mid,left,right);
                if(nums[mid]<target)
                    left=mid+1;
                else
                    right=mid-1;
            }
            return new int[2]{-1,-1};
        }
        
        private int[] findRange(int[] nums,int index,int leftI,int rightI)
        {
            int target=nums[index];
            int left=index,right=index;
            while(left - 1 >= leftI && nums[left-1]==target)
                left--;
            while(right + 1 <= rightI && nums[right+1]==target )
                right++;
            return new int[2]{left,right};
        }
    }

Log in to reply
 

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