35. Search Insert Position

📘 題目敘述

給定一個已經依照遞增順序排序、且元素彼此不同的整數陣列 nums，以及一個整數 target。

如果 target 已經在陣列中，請回傳它的索引。
如果不在，請回傳它應該插入的位置，使得插入後陣列仍然保持排序。

而且題目要求演算法時間複雜度必須是 O(log n)。

條件限制

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 中的值彼此不同，且已依遞增順序排列
• -10^4 <= target <= 10^4

🧠 解題思路

我這題的想法就是標準 binary search。

因為陣列本來就已經排序好了，所以我可以用二分搜去找：

• target 是不是存在
• 如果不存在，那它應該落在哪個位置

我這份寫法維護一個搜尋區間 [l, r)，也就是：

• l 會指向目前可能答案的左邊界
• r 會指向目前可能答案的右邊界外一格

每次取中間位置 m：

• 如果 nums[m] > target，代表答案在左半邊
• 如果 nums[m] < target，代表答案在右半邊
• 如果剛好相等，就直接回傳 m

如果最後都沒找到，l 停下來的位置，就是 target 應該插入的位置。

所有變數

• l：binary search 的左邊界
• r：binary search 的右邊界外一格
• m：目前區間的中間位置

🪜 主要流程步驟

1. 先設定 binary search 的搜尋區間

我先把左邊界設成 0，右邊界設成 nums.size()：

int l = 0, r = nums.size();

這代表我搜尋的是一個左閉右開區間 [l, r)。

這樣寫的好處是：

• 如果 target 比所有元素都大，最後答案可以自然停在 nums.size()
• 也就是插在陣列最後面

2. 只要區間還有範圍，就一直取中間位置

接著我用：

while (l < r) {

表示只要目前區間還沒縮到空，就繼續做 binary search。

中間位置用：

int m = (l + r) / 2;

來取得。

這樣每次都能把搜尋範圍大約砍半。

3. 根據 nums[m] 和 target 的大小關係縮小區間

接著我比較 nums[m] 和 target。

如果：

if (nums[m] > target) {
    r = m;
}

表示中間值太大了，
那 target 如果存在，或者它應該插入的位置，都一定在左半邊，所以把右邊界縮成 m。

如果：

else if (nums[m] < target) {
    l = m + 1;
}

表示中間值太小了，
那答案一定在右半邊，所以把左邊界移到 m + 1。

如果剛好：

else {
    return m;
}

表示真的找到 target，直接回傳它的索引。

4. 如果最後沒找到，l 就是應該插入的位置

如果 while 結束，表示整個搜尋區間已經縮到空，而且過程中沒有找到 target。

這時候 l 停下來的位置，就是 target 應該插入的位置，所以直接：

return l;

這點可以這樣理解：

• l 前面的數都小於 target
• l 以及後面的數都大於等於 target

所以把 target 插在 l，剛好可以維持排序。

⏱️ 複雜度

設 n = nums.length。

• 時間複雜度：O(log n)
  每次 binary search 都把搜尋範圍縮小一半。
• 空間複雜度：O(1)
  只用了固定數量的變數。

💻 程式碼實作

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while (l < r) {
            int m = (l + r) / 2;
            if (nums[m] > target) {
                r = m;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                return m;
            }
        }
        return l;
    }
};

🔗 題目連結

https://leetcode.com/problems/search-insert-position/