34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
示例1：
输入：nums = [5,7,7,8,8,10], target = 8输出：[3,4]
示例2：
输入：nums = [5,7,7,8,8,10], target = 6输出：[-1,-1]
示例3：
输入：nums = [], target = 0输出：[-1,-1]
解题方法：二分查找
class Solution {
func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
let first = searchFirst(nums, target)
let last = searchLast(nums, target)
return [first, last]
}
func searchFirst(_ nums: [Int], _ target: Int) -> Int {
var left = 0
var right = nums.count - 1
while left <= right {
let mid = left + (right - left) / 2
if nums[mid] == target {
if mid == left || nums[mid - 1] != target {
return mid
} else {
right = mid - 1
}
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
func searchLast(_ nums: [Int], _ target: Int) -> Int {
var left = 0
var right = nums.count - 1
while left <= right {
let mid = left + (right - left) / 2
if nums[mid] == target {
if mid == right || nums[mid + 1] != target {
return mid
} else {
left = mid + 1
}
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
}
解题思路:
本题是要找到第一个和最后一个满足等于 target 的元素的位置，不存在则返回 -1。
复杂度分析
- 时间复杂度：
O(logn)，其中n为数组的长度。 - 空间复杂度：
O(1)。