Interview Classic 150 Questions P4 Find the Median of Two Sorted Arrays

---

Timeline

Timeline

2025-12-04

init

Divide and Conquer

---

Problem:

P4 Find the 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 it can be optimized (when one array is already empty, the median can be calculated directly)

#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 method:

According to the definition of the median:

• whenm+nWhen it is odd, the median is the(m+n+1)/2elements
• 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 (exclude k/2 impossible elements each time)

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

• Case 1:pivot1 <= pivot2

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

  • Therefore:nums1topk/2all deleted

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

• Case 2:pivot2 < pivot1

  • Similarly:nums2topk/2deletions
  • Update:index2 += k/2,k -= k/2

Additionally, there are three edge cases; handle them at the beginning of the loop:

1. One array is already empty.

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

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

2. k == 1

1st smallest = minimum of the two arrays

return min(nums1[index1], nums2[index2]);

3. Normal binary deletion

Continuously reducekUntil: k == 1

Code:

#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 in ... less than or equal to pivot1 the elements are nums1[0 .. k/2-2] in total k/2-1 piece
                 * nums2 in ... less than or equal to pivot2 the elements are nums2[0 .. k/2-2] in total k/2-1 piece
                 * Take pivot = min(pivot1, pivot2)，in the two arrays, less than or equal to pivot the elements
                 * in total will not exceed (k/2-1) + (k/2-1) <= k-2 piece
                 * In this way pivot itself can at most be the k-1 Smallest Element
                 * if pivot = pivot1，Then nums1[0 .. k/2-1] none of them can be the k Smallest Element。
                 * all of these elements "Delete"，the remaining as the new nums1 Array
                 * if pivot = pivot2，Then nums2[0 .. k/2-1] none of them can be the k Smallest Element。
                 * all of these elements "Delete"，the remaining as the new nums2 Array
                 * Since we "Delete" some elements（These elements are all than the k the smaller elements are smaller），Therefore, we 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) {
                        // edge 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
                        k = (total_len + 1) / 2;
                        return getKthElement(nums1, nums2, k);
                } else { // Even
                        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: I didn’t write it out hahaha, this binary search is a bit hard to think of