# ac solution code

• 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
}
``````

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