筆記: 【演算法新手村】[初階]筆記02 - 初識二分之常見問題

題目翻譯(by Gemini)

給定一個已排序且元素皆不重複的整數陣列，以及一個目標值（target）：

• 如果目標值存在於陣列中，回傳其索引值（index）。
• 如果目標值不存在，回傳它依序被插入陣列後應有的索引位置。

你必須撰寫一個 時間複雜度為 O(logn) 的演算法。

解題思路

看到 時間複雜度為 O(logn) 就可以優先考慮看看二分可不可以實現，而這題可以。
看到題目，其實是我之前提過的原題：找 >= target 之最左位置，當然這題你可以直接用最基本的二分分情況去做：找到就返回；沒找到就 去找插在哪裡，因為這題有說 元素皆不重複 ，所以這樣也是可以的，不然就會變成可能有很多個target，這邊的寫法用的是 找 >= target 之最左位置的寫法，唯一需要注意的是我們的ans只有在 查找到的元素 >= target 時更新，需要特別注意到假如所有元素都 < target 時完全不會記錄答案，所以我們將ans初始化為-1(-1是因為在後續計算中不可能出現-1這個值，可以在最後檢查，假如是-1就代表要插入在最後面，因為這是只有全部元素都比target小的狀況下才會發生)

程式碼實作 (C++)

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

C的相似度也非常高，所以不多加贅述。