Cover image for Interview Classic 150 Questions P4 Find Median of Two Sorted Arrays

Interview Classic 150 Questions P4 Find Median of Two Sorted Arrays

(Updated: )
algorithm
, , ,
Timeline

timeline

2025-12-04

init

divide and conquer

Title:

P4 Find Median of Two Sorted Arrays

https://leetcode.cn/problems/median-of-two-sorted-arrays/description/?envType=study-plan-v2&envId=top-interview-150

O((m+n)/2) solution, merge arrays, but can be optimized (when one array is empty, the median can be calculated directly)

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <vector>
using std::vector;

class Solution {
    public:
        double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
        {
                int m = nums1.size(), n = nums2.size();
                int last_num;

                int mi = 0, ni = 0;
                int index = 0;
                int total = m + n;
                double res = 0;

                while (mi < m || ni < n) {
                        if (mi < m && ni < n) {
                                if (nums1[mi] < nums2[ni]) {
                                        last_num = nums1[mi++];

                                } else {
                                        last_num = nums2[ni++];
                                }
                        } else if (mi >= m && ni < n) {
                                last_num = nums2[ni++];

                        } else if (mi < m && ni >= n) {
                                last_num = nums1[mi++];
                        }


                        if (total % 2 == 0) {
                                if(index == total / 2 - 1){
                                        res += last_num;
                                }else if(index == total / 2){
                                        res += last_num;
                                        res = (double) res/2;
                                        break;
                                }
                        } else {
                                if (index == total / 2) {
                                        res = last_num;
                                        break;
                                }
                        }
                        index++;
                }
                return res;
        }
};

Binary search:

According to the definition of median:

  • Whenm+nis odd, the median is the(m+n+1)/2th element
  • Whenm+nWhen it is even, the median is the(m+n)/2th element and the(m+n)/2+1th element’s average.

Therefore, this problem can be transformed into finding the k-th smallest number in two sorted arrays, where k is(m+n)/2or(m+n)/2+1。

The core idea is: delete k/2 elements each time (each time exclude k/2 impossible elements)

Let:pivot1 = nums1[k/2-1],pivot2 = nums2[k/2-1], compare:pivot1 vs pivot2, initialindex1andindex2are both 0

  • Case 1:pivot1 <= pivot2

    • Explanation:nums1[0...k/2-1]cannot be the k-th smallest, becausenums1 <= pivot1at mostk/2pieces,nums2 <= pivot2at mostk/2-1pieces, total<= k-1

    • Therefore:nums1Firstk/2delete all items

    • Update:index1 += k/2,k -= k/2

  • Case 2:pivot2 < pivot1

    • Similarly:nums2firstk/2delete items
    • Update:index2 += k/2,k -= k/2

In addition, there are three boundary cases, handle boundaries first at the start of the loop:

  1. An array is already empty

For example:nums1 = [],nums2 = [1,2,3,4], the k-th smallest is:nums2[k-1]

1
2
3
4
if (index1 == m)
    return nums2[index2 + k - 1];
if (index2 == n)
    return nums1[index1 + k - 1];
  1. k == 1

1st smallest = minimum of two arrays

1
return min(nums1[index1], nums2[index2]);
  1. Normal binary deletion

Continuously reducekuntil: k == 1

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <vector>
using std::vector;

class Solution {
    public:
        int getKthElement(const vector<int> &nums1, const vector<int> &nums2, int k)
        {
                /*
                 * Main idea：To find the k (k>1) smallest element，then take
                 * pivot1 = nums1[k/2-1] and pivot2 = nums2[k/2-1] for comparison
                 * Here "/" denotes integer division
                 * nums1 less than or equal to pivot1 the elements that are nums1[0 .. k/2-2] total k/2-1 elements
                 * nums2 less than or equal to pivot2 the elements that are nums2[0 .. k/2-2] total k/2-1 elements
                 * take pivot = min(pivot1, pivot2)，in the two arrays, less than or equal to pivot the elements
                 * total will not exceed (k/2-1) + (k/2-1) <= k-2 elements
                 * thus pivot itself can only be at most the k-1 smallest element
                 * if pivot = pivot1，then nums1[0 .. k/2-1] cannot be the k smallest element。
                 * take all these elements "delete"，the remaining as new nums1 array
                 * if pivot = pivot2，then nums2[0 .. k/2-1] cannot be the k smallest element。
                 * take all these elements "delete"，the remaining as new nums2 array
                 * since we "delete" some elements（these elements are all smaller than the k smaller element），therefore need to
                 * modify k the value of，subtract the number of deleted elements
                 */

                int m = nums1.size();
                int n = nums2.size();
                int idx1 = 0, idx2 = 0;
                int new_idx1, new_idx2, pivot1, pivot2;

                while (true) {
                        // boundary case
                        if (idx1 == m)
                                return nums2[idx2 + k - 1];

                        if (idx2 == n)
                                return nums1[idx1 + k - 1];

                        if (k == 1)
                                return std::min(nums1[idx1], nums2[idx2]);

                        // normal case
                        new_idx1 = std::min(idx1 + k / 2 - 1, m - 1);
                        new_idx2 = std::min(idx2 + k / 2 - 1, n - 1);
                        pivot1 = nums1[new_idx1];
                        pivot2 = nums2[new_idx2];

                        if (pivot1 <= pivot2) {
                                k -= new_idx1 - idx1 + 1;
                                idx1 = new_idx1 + 1;
                        } else {
                                k -= new_idx2 - idx2 + 1;
                                idx2 = new_idx2 + 1;
                        }
                }
        }

        double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
        {
                int total_len = nums1.size() + nums2.size();
                int k, val1, val2;

                if (total_len % 2 == 1) { // odd number
                        k = (total_len + 1) / 2;
                        return getKthElement(nums1, nums2, k);
                } else { // even number
                        k = total_len / 2;
                        val1 = getKthElement(nums1, nums2, k);

                        k = total_len / 2 + 1;
                        val2 = getKthElement(nums1, nums2, k);

                        return (val1 + val2) / 2.0;
                }
        }
};

hot 100 rewrite: didn’t write it out hahaha, this binary search is a bit hard to think of