95.在排序数组中查找元素的第一个和最后一个位置
题目
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。
请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 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]
思路
数组是排序好的(升序)，这就意味着相同的数字都挤在一起。
不用线性扫描，而是用两次二分查找:
-
第一次二分: 找第一个等于target的位置
- 找到target时，不着急返回，继续往左边找，看看还有没有更早的
-
第二次二分: 找最后一个等于target的位置 找到target时，不着急返回，继续往右找，看看还有没有更晚的
fun searchRange(nums: IntArray, target: Int): IntArray {
// 先找第一个位置
val first = findFirst(nums, target)
// 再找最后一个位置
val last = findLast(nums, target)
return intArrayOf(first, last)
}
// 找第一个等于target的位置
private fun findFirst(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size - 1
var result = -1
while (left <= right) {
val mid = left + (right - left) / 2
when {
nums[mid] == target -> {
result = mid // 记录当前位置
right = mid - 1 // 继续往左边找，看还有没有更早的
}
nums[mid] < target -> left = mid + 1
else -> right = mid - 1
}
}
return result
}
// 找最后一个等于target的位置
private fun findLast(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size - 1
var result = -1
while (left <= right) {
val mid = left + (right - left) / 2
when {
nums[mid] == target -> {
result = mid // 记录当前位置
left = mid + 1 // 继续往右边找，看还有没有更晚的
}
nums[mid] < target -> left = mid + 1
else -> right = mid - 1
}
}
return result
}
Q：能不能只用一次二分就搞定？
A：可以，但比较复杂。思路是先二分找到一个target的位置，然后向两边扩展找到边界。但在最坏情况下（全是target）会退化成O(n)。所以标准解法还是两次二分。
Q：如果数组为空怎么办？
A：代码已经处理好了，findFirst和findLast都会返回-1。
Q：这和普通的二分查找有什么区别？
A：普通二分找到target就直接返回了。这里找到后不着急走，还要继续找边界，这就是"二分查找边界"的技巧。
复杂度
- 时间复杂度: O(log n) — 两次二分，每次O(log n)
- 空间复杂度: O(1) — 只用了几个变量
- 邮箱 ：charon.chui@gmail.com
- Good Luck!