ac solution code


  • 0

    The basic idea is to do two binary search: 1) find first matched position i; 2) find last matched position j. Then return [i, j]

        /*
         Solution1. time = O(2*lgN) = O(lgN); space = O(1)
         */
        func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
            var res = [-1, -1]
            var left = 0, right = nums.count - 1
            while (left <= right) {// Binary Search: find first match
                let mid = (left + right) / 2
                if (nums[mid] < target) {
                    left = mid + 1 // advance left to mid + 1
                } else {
                    right = mid - 1 // rewind right to mid - 1
                }
            }
            res[0] = (left <= nums.count - 1 && nums[left] == target) ? left : -1
    
            right = nums.count - 1// No need to reset left, it's the first matched position. 0....left(first match).....right....n-1
            while (left < right) {// Binary Search: find last match
                // TRICK: mid should +1 here to ensure result trends to upper bound, as divide rule of integer selects the lower number as integer, e.g. 3/2= 1.
                let mid = (left + right) / 2 + 1
                if nums[mid] <= target {
                    left = mid // mid no need to + 1, as we already did it above
                } else {
                    right = mid - 1
                }
            }
            res[1] = (left <= nums.count - 1 && nums[left] == target) ? left : -1
            return res
        }
    

Log in to reply
 

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