runtime 0 ms, beats 100% of cpp submissions
O(log(n)) solution with explanation

tags: binary search

Search Insert Position

📖 description

給定一個 sorted array nums ，與一個需要插入的數字 target ，回傳可以插入的位置，在使的該 array 仍然是 sorted 的前提下，邀求時間複雜度為 O(log(n)) 。

🧠 solution

正常的 binary search ，如果找的到 target 就回傳當下的 index ，如果找不到就回傳 l 就好。

⏳ time complexity

binary search 時間複雜度為 O(log(n))
總時間複雜度 O(log(n))

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int searchInsert(vector<int>& nums, int t) {
        if(t<nums[0]) return 0;                     // 邊緣測資
        else if(t>nums.back()) return nums.size();  // 邊緣測資
        int l = 0,r = nums.size()-1;
        int m;
        while(r>=l){
            m = (l+r)/2;
            if(nums[m]==t){
                return m;
            }
            else if(nums[m]<t){
                l = m+1;
            }
            else{
                r = m-1;
            }
        }
        return l;
    }
};