Leetcode 35 - Search Insert Position

題目

Problem#

題目給你排序好的陣列 nums 和整數 target，問你如果 target 存在於 nums 中則回傳 index；反之，回傳他可能插入的第一個 index

想法#

其實是問你陣列中第一個 >= target 的數字之位置，二分搜裸題

• 時間複雜度: $\mathcal{O}(\log{n})$
• 空間複雜度: $\mathcal{O}(1)$

AC Code#

Copy

class Solution
{
public:
    int searchInsert(vector<int>& n, int k)
    {
        // [l, r) 半開區間
        int l = 0, r = n.size();
        while(l < r)
        {
            int mid = (l+r) / 2;
 
            if(n[mid] >= k)
                r = mid;
            else
                l = mid+1;
        }
 
        return l;
    }
 
    int stl(vector<int>& n, int k)
    {
        return lower_bound(n.begin(), n.end(), k) - n.begin();
    }
};

view raw leetcode/35.cpp delivered with ❤ by emgithub