給定一個排序好的整數陣列
nums（不含重複值）和一個目標值target，找到目標值在陣列中的索引。如果不存在，回傳它應該被插入的位置，使陣列維持有序。
Example:
Input: nums = [1,3,5,6], target = 5 Output: 2
Intuition
TIP
找到第一個大於等於 target 的位置，就是插入點。
- 本質上就是在排序陣列中找 lower bound
- 如果 target 存在，回傳其索引；如果不存在，回傳第一個比它大的元素位置
Approaches
1. Linear Scan — O(n) / O(1)
- Idea: 從左往右掃描，找到第一個 >= target 的位置
- Time:
O(n) - Space:
O(1)
Linear Scan Code
class Solution {
fun searchInsert(nums: IntArray, target: Int): Int {
for (i in nums.indices) {
if (nums[i] >= target) return i
}
return nums.size
}
}⭐ 2. Binary Search — O(log n) / O(1)
- Idea: 使用二分搜尋找到第一個 >= target 的位置（lower bound）
- Time:
O(log n) - Space:
O(1)
class Solution {
fun searchInsert(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size
while (left < right) {
val mid = left + (right - left) / 2
if (nums[mid] < target) {
left = mid + 1
} else {
right = mid
}
}
return left
}
}WARNING
注意 right 初始值為 nums.size（不是 nums.size - 1），因為插入位置可能在陣列最末端之後。
🔑 Takeaways
- Pattern: Lower Bound 二分搜尋模板
- Key trick: 這是最基礎的 lower bound 模板，
left < right配合right = mid，最終left就是第一個 >= target 的位置