C# O(Log(n)) Solution. 3 Binary Search -- 1st to get the target, 2nd to find leftwall, 3rd to find rightwall


  • 0
    L
    public class Solution {
        public int[] SearchRange(int[] nums, int target) {
            int begin = 0, end = nums.Length - 1;
            int mid = 0;
            int[] result = {-1, -1};
            if(nums.Length == 0) return result;
            if(nums.Length == 1 && nums[0] == target)
            {
                result[0] = 0;
                result[1] = 0;
                return result;
            }
    
            while(begin <= end)
            {
                mid = (begin + end) / 2;
                if(begin == end)
                {
                    if(target == nums[mid])
                    {
                        result[0] = begin;
                        result[1] = end;
                        return result;
                    }
                    else
                        return result;
                }
                if(target > nums[mid])
                    begin = mid + 1;
                else if(target < nums[mid])
                    end = mid;
                else
                {
                    //Get left wall
                    int tmp = mid;
                    while(begin <= tmp)
                    {
                        if(begin == tmp)
                            break;
                        if(nums[(begin + tmp)/2] == target)
                            tmp  = (begin + tmp)/2;
                        else 
                            begin = (begin + tmp)/2 + 1;
                    }
                    //Get right wall
                    tmp = mid;
                    while(tmp <= end)
                    {
                        if(tmp == end)
                            break;
                        if(nums[(tmp + end)/2] == target)
                            tmp = (tmp + end)/2 + 1;
                        else 
                            end  = (tmp + end)/2;
                    }
                    result[0] = begin;
                    result[1] = nums[tmp] == target?tmp : tmp - 1;
                    return result;
                }
            }
            
            return result;
        }
    }

Log in to reply
 

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