Intuition#

找到第一個大於等於 target 的位置，就是插入點。

• 本質上就是在排序陣列中找 lower bound
• 如果 target 存在，回傳其索引；如果不存在，回傳第一個比它大的元素位置

Approaches#

1: Linear Scan#

• 概念: 從左往右掃描，找到第一個 >= target 的位置
• 時間複雜度: O(n)
• 空間複雜度: O(1)

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#

• 概念: 使用二分搜尋找到第一個 >= target 的位置（lower bound）
• 時間複雜度: O(log n)
• 空間複雜度: 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
    }
}

注意 right 初始值為 nums.size（不是 nums.size - 1），因為插入位置可能在陣列最末端之後。

🔑 Takeaways#

• Pattern: Lower Bound 二分搜尋模板
• 關鍵技巧: 這是最基礎的 lower bound 模板，left < right 配合 right = mid，最終 left 就是第一個 >= target 的位置