runtime 39 ms, beats 93.16% of cpp submissions
O(log(m+n)) solution with explanation

tags: binary search

median of Two Sorted Arrays

📖 description

給定兩個 sorted array ，長度分別為 m 與 n，並回傳他們 merge 完後的中位數。
要求 worst case 時間複雜度為 O(log(m+n))

🧠 solution

在第一眼看到這個題目時最直接的想法是先將兩個陣列 merge 起來，並回傳中位數即可，但這樣做的時間複雜度是 O(m+n) ，遠遠超過了題目的限制，而看到 log 系列最直接的想法要不就是 sort ，要不就是 binary search ，一開始就給了 sorted array ，所以大概就是 binary search 的應用了。

要找到 merge 完陣列的中位數，其實就是指該數的左右元素個數一樣，於是我們就可以應用 binary search 來解決問題了，只要找到前 (m+n)/2 的元素就代表找到了，並且因為 (m+n)/2 的數值固定，所以只需要在其中一個陣列中尋找切割點 cut_point ，另一個就是前面 (m+n)/2-cut_point 個元素，兩個陣列的左區間合在一起就是 merge 完的左區間了。

在更新 binary search 的區間時，就有許多地方需要注意了， cut_point 為當前陣列右區間的開頭，cut_point-1 表示當前陣列左區間的結尾，而找到正確的切割點的標準如下。

變數說明

high : binary search 的搜尋上限
low : binary search 的搜尋下限
cut1 : 表示陣列1的切割點
cut2 : 表示陣列2的切割點
l1 : 表示陣列1左區間的尾巴
l2 : 表示陣列2左區間的尾巴
r1 : 表示陣列1右區間的開頭
r2 : 表示陣列2右區間的開頭

要模擬 merge 的過程必須要滿足一個條件， case1 陣列1左區間的尾巴要比陣列2右區間的開頭還要小，也就是 l1 <= r2 ， case2 以及陣列2左區間的尾巴要比陣列1右區間的開頭還要小，也就是 l2 <= r1 ，在不滿足的狀況下才更新搜尋區間，否則回傳答案。

case1 不滿足代表陣列1左區間的尾巴太大，將 high 更新。
case2 不滿足代表陣列1右區間的開頭太大，將 low 更新。

⏳ time complexity

對較小的陣列做 binary search
總時間複雜度 O(log(min(m+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
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2){
        int m = nums1.size(),n = nums2.size();
        if(m>n) return findMedianSortedArrays(nums2,nums1); // 只對較短的陣列做二分搜
        int low = 0, high = m;
        while(low <= high){
            int cut1 = (high+low)/2;                        // 對第一個陣列做2分搜
            int cut2 = (m+n)/2-cut1;                        // 拿剩下的位置
            int l1 = cut1 == 0 ? INT_MIN : nums1[cut1-1];   // 表示陣列1左區間的尾巴
            int l2 = cut2 == 0 ? INT_MIN : nums2[cut2-1];   // 表示陣列2左區間的尾巴
            int r1 = cut1 == m ? INT_MAX : nums1[cut1];     // 表示陣列1右區間的開頭
            int r2 = cut2 == n ? INT_MAX : nums2[cut2];     // 表示陣列2右區間的開頭
            if(l1 > r2){                                    // case1
                high = cut1-1;
            }
            else if(l2 > r1){                               // case2
                low = cut1+1;
            }
            else{                                           // 條件滿足
                if((n+m)%2==0){                             // 如果元素各數為偶數
                    // merge 完較大的左區間尾巴+較小的右區間開頭
                    return (max(l1,l2)+min(r1,r2))/2.0;     
                }
                else{                                       // 為奇數
                    return min(r1,r2);                      // 較小的右區間開頭放前面
                }
            }
        }
        return -1;
    }
};