一道二分

Posted on In

一道二分

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be \(O(\log (m+n))\).

1
2
3
4
5
6
typedef Comparable int;
Comparable find_median(const vector<Comparable> &l1, const vector<Comparable> &l2)
/*
Pre:  The ordered lists l1,l2 are not all empty.
Post: The median of the two lists combined in order is returned. If the size of the merged list is even, then the first of the two medians is returned. For exmaple, l1 =(1,2), l2=(1,3,4,5), then 2 is returned.
*/

Solution

find the \(k\)th min number, where: \[ k = \begin{cases} \dfrac{m+n}{2},\ \text{when}\ m+n\ \text{is even},\\\\ \dfrac{m+n+1}{2},\ \text{when}\ m+n\ \text{is odd}. \end{cases} \] To find the number, compare \(A[k/2-1]\) and \(B[k/2-1]\):

  • if \(A[k/2-1] \leq B[k/2-1]\), remove \(A[0:k/2-1]\),
  • if \(A[k/2-1] > B[k/2-1]\), remove \(B[0:k/2-1]\).

and some cases:

  • if \(A[k/2-1]\) or \(B[k/2-1]\) is out of bound, choose the last element of the array.
  • if an array is empty, find the kth min number in the other.
  • if \(k=1\), return \(\min(A[0], B[0])\)
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
int getK(const vector<Comparable> &l1, const vector<Comparable> &l2, int k){
    int i1 = 0, i2 = 0;
    while(1){
        if(i1 == l1.size()){
            return l2[i2 + k - 1];
        }
        if(i2 == l2.size()){
            return l1[i1 + k - 1];
        }
        if(k == 1){
            return min(l1[i1], l2[i2]);
        }
        int p1 = min(i1 + k / 2 - 1, (int)l1.size() - 1);
        int p2 = min(i2 + k / 2 - 1, (int)l2.size() - 1);
        if(l1[p1] <= l2[p2]){
            k -= p1 - i1 + 1;
            i1 = p1 + 1;
        }
        else{
            k -= p2 - i2 + 1;
            i2 = p2 + 1;
        }
    }
}

Comparable find_median(const vector<Comparable> &l1, const vector<Comparable> &l2){
    int l = l1.size() + l2.size();
    if(l%2 == 1){
        return getK(l1, l2, (l + 1) / 2);
    }
    else{
        return getK(l1, l2, l / 2);
    }
}