給定一個按非遞減順序排列的整數陣列
nums，找出目標值target的起始位置和結束位置。如果不存在，回傳[-1, -1]。要求O(log n)時間複雜度。
Example:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Intuition
TIP
分別用兩次二分搜尋找 lower bound（第一個 >= target）和 upper bound（第一個 > target）。
- 第一次二分找第一個 >= target 的位置（lower bound）
- 第二次二分找第一個 > target 的位置（upper bound）
- 結束位置 = upper bound - 1
Approaches
1. Linear Scan — O(n) / O(1)
- Idea: 從左找第一個 target，從右找最後一個 target
- Time:
O(n) - Space:
O(1)
Linear Scan Code
class Solution {
fun searchRange(nums: IntArray, target: Int): IntArray {
var first = -1
var last = -1
for (i in nums.indices) {
if (nums[i] == target) {
if (first == -1) first = i
last = i
}
}
return intArrayOf(first, last)
}
}⭐ 2. Two Binary Searches — O(log n) / O(1)
- Idea: 分別二分搜尋 lower bound 和 upper bound
- Time:
O(log n) - Space:
O(1)
class Solution {
fun searchRange(nums: IntArray, target: Int): IntArray {
val left = lowerBound(nums, target)
if (left == nums.size || nums[left] != target) {
return intArrayOf(-1, -1)
}
val right = lowerBound(nums, target + 1) - 1
return intArrayOf(left, right)
}
// 找第一個 >= target 的位置
private fun lowerBound(nums: IntArray, target: Int): Int {
var lo = 0
var hi = nums.size
while (lo < hi) {
val mid = lo + (hi - lo) / 2
if (nums[mid] < target) {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
}WARNING
巧妙地用 lowerBound(target + 1) - 1 取代 upper bound 的實作，只需要一個通用的 lower bound 函式。
🔑 Takeaways
- Pattern: Lower Bound / Upper Bound 二分搜尋
- Key trick:
lowerBound(target)找起始位置，lowerBound(target + 1) - 1找結束位置。這個技巧讓你只需要維護一個 lower bound 模板就能解決各種邊界問題