C# solution: binary search with explanation


  • 0
    B
    • Why left = mid + 1 & right = mid?
      because when the length of an array is even, mid will get the middle on the left, such as [0,1] mid = 0.
      If we use left = mid & right = mid - 1, it may cause the infinite loop, always 0 = 0, 0 = 0, 0 = 0, 0 = 0 ...

    • When we calculate the right edge, in this situation: [8, 10] target = 8, because we run left = mid + 1, so the final result is left == right == 1, [1] = 10, so we have to see whether we need to -1 on the index.

    C# also provides List<T>.BinarySearch()
    Please check here:
    https://msdn.microsoft.com/en-us/library/w4e7fxsh(v=vs.110).aspx

    public class Solution 
    {
        public int[] SearchRange(int[] nums, int target) 
        {
            if (nums.Length == 0) return new int[]{-1,-1};
    
            var n = nums.Length;
            var left = 0;
            var right = n - 1;
    
            // start
            while(left < right)
            {
                var mid = left + (right - left) / 2;
    
                if (nums[mid] == target)
                {
                    right = mid;
                }
                else if (nums[mid] < target)
                {
                    left = mid + 1;
                }
                else if (nums[mid] > target)
                {
                    right = mid;  
                }
            }
    
            var start = left;
    
            if (nums[start] != target) return new int[]{-1,-1};
    
            // end
            left = start;
            right = n - 1;
    
            while(left < right)
            {
                var mid = left + (right - left) / 2;
    
                if (nums[mid] == target)
                {
                    left = mid + 1;
                }
                else if (nums[mid] < target)
                {
                    left = mid + 1;
                }
                else if (nums[mid] > target)
                {
                    right = mid;
                }
            }
    
            // if [8,10] target is 8, but left = right = 1, so need -1
            var end = nums[right] == target ? right : right - 1;
    
            return new int[]{start, end};                                                                                                            
        }
    }
    

Log in to reply
 

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