Median of Two Sorted Arrays C++ program. Programming competition/Interview questions. (logic explained)

 Median of Two Sorted Arrays C++ program. Programming competition/Interview questions. (logic explained) 

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)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]

Output: 2.50000

Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

1 <= m + n <= 2000

-106 <= nums1[i], nums2[i] <= 106

Explanation:

The solution below is written in C++ and uses the binary search algorithm to find the median of two sorted arrays nums1 and nums2. The basic idea behind this solution is to use binary search to find the partition point where the elements on the left side of the partition point have the same count as the elements on the right side of the partition point. This way, we can find the median by taking the average of the maximum element on the left partition and the minimum element on the right partition.

The solution has a public method findMedianSortedArrays which takes two input arrays nums1 and nums2 and returns the median value as a double type.

First, the solution checks if m, the length of nums1, is greater than n, the length of nums2, and swaps the two arrays if that is the case. This is done because we want m to always be the smaller array for ease of calculation.

Next, the solution declares two variables iMin and iMax and sets iMin to 0 and iMax to m. The variable halfLen is also declared and set to (m + n + 1) / 2, which is the total number of elements divided by 2 and rounded up if the total number of elements is odd.

The solution then enters a while loop, which continues until iMin is greater than iMax. Inside the while loop, the solution finds the middle point i of the search space by taking the average of iMin and iMax. Then, it calculates j as halfLen - i, which is the equivalent partition point in the other array.

The solution then checks if the current partition point i is in the right place by comparing the elements at nums1[i - 1] and nums2[j - 1]. If i is too small and nums2[j - 1] is greater than nums1[i], the search space is updated by setting iMin to i + 1. If i is too big and nums1[i - 1] is greater than nums2[j], the search space is updated by setting iMax to i - 1.

If the partition point i is in the right place, the solution finds the maximum value of nums1[i - 1] and nums2[j - 1] and stores it in maxLeft. If the total number of elements is odd, maxLeft is returned as the median. If the total number of elements is even, the solution also finds the minimum value of nums1[i] and nums2[j] and stores it in minRight. The median is then calculated as the average of maxLeft and minRight and returned.

The solution is guaranteed to run in O(log(min(m, n))) time, as each iteration of the while loop reduces the search space by half, and the total number of iterations is limited to the logarithmic value of the smaller array length min(m, n).

Here's one approach to solve this problem in C++:

Code:

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 iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < m && nums2[j - 1] > nums1[i]) {
                iMin = i + 1;
            } else if (i > 0 && nums1[i - 1] > nums2[j]) {
                iMax = i - 1;
            } else {
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = nums2[j - 1];
                } else if (j == 0) {
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }
                int minRight = 0;
                if (i == m) {
                    minRight = nums2[j];
                } else if (j == n) {
                    minRight = nums1[i];
                } else {
                    minRight = min(nums1[i], nums2[j]);
                }
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
};

Conclusion:

This solution uses binary search to find the position of the median in the two arrays. The run time complexity is O(log(min(m, n))) as the size of the search space is reduced by half in each iteration.