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

tags: binary search

Find First and Last Position of Element in Sorted Array

📖 description

給定一個 sorted array nums ，找到 target 元素出現的頭跟尾，邀求時間複雜度為 *O(log(n))*。

ex.
    nums = [5, 7, 7, 8, 8, 10]
    target = 8

    元素 8 在 nums 出現的區間是 [3,4]



    nums = [5, 7, 7, 7, 8, 9, 9]
    target = 7

    元素 7 在 nums 出現的區間是 [1,3]

🧠 solution

使用兩次 binary search 找下限與上限，尋找上限時可以透過把找到的下陷當成 l 來檢少運算。

也可以先使用 binary search 找到其中一個符合 target 的數值後，針對左右 linear search 上下限，但這樣做的 worst case 是 O(n) ，因為有可能整個陣列都是同一個數字。

⏳ 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
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int t) {
        vector<int> ans{-1,-1};
        if(nums.size()==0) return ans;
        int l = 0,r = nums.size()-1;
        while(r>=l){    // 第一個 binary search 找下限
            int m = (l+r)/2;
            if(nums[m]<t){
                l = m+1;
            }
            else{
                if(nums[m] == t){   // 特殊狀況，如果已經找到 target ，則當前 index 可能是答案，先儲存
                    ans[0] = m;
                }
                r = m-1;
            }
        }
        l = max(0,r), r = nums.size()-1; // l 可以先從之前的下限開始找起
        while(r>=l){
            int m = (l+r)/2;
            if(nums[m]>t){
                r = m-1;
            }
            else{
                if(nums[m] == t){   // 特殊狀況，如果已經找到 target ，則當前 index 可能是答案，先儲存
                    ans[1] = m;
                }
                l = m+1;
            }
        }
        return ans;
    }
};