4. Median of Two Sorted Arrays - Detailed Explanation

Problem Statement

You are given two sorted arrays, nums1 and nums2, of sizes m and n respectively. The task is to find the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)). The median is defined as the middle element when the two arrays are combined in sorted order. If the total number of elements is odd, the median is the middle element; if even, it is the average of the two middle elements.

Examples

Example 1

• Input: nums1 = [1, 3], nums2 = [2]
• Output: 2.0
• Explanation:
  Combined sorted array: [1, 2, 3]. The middle element is 2.

Example 2

• Input: nums1 = [1, 2], nums2 = [3, 4]
• Output: 2.5
• Explanation:
  Combined sorted array: [1, 2, 3, 4]. The two middle elements are 2 and 3, so the median is (2 + 3) / 2 = 2.5.

Approaches

There are several ways to solve this problem:

1. Merging Approach

• Idea:
  Merge the two arrays into one sorted array and then compute the median.
• Time Complexity: O(m+n)
• Drawback:
  Although simple, merging the entire arrays is not optimal if we only need the median.

2. Binary Search Partition (Optimal)

• Idea:
  Use binary search on the smaller array to partition both arrays into two halves such that:
  • The left half contains the first half of the combined sorted elements.
  • The right half contains the second half.
  The partition is chosen so that every element in the left half is less than or equal to every element in the right half. Then:
  • If the total number of elements is odd, the median is the minimum element of the right half.
  • If even, the median is the average of the maximum element from the left half and the minimum element from the right half.
• Time Complexity: O(log(min(m, n)))
• Pros:
  Efficient and meets the logarithmic time requirement.

Step-by-Step Walkthrough of the Binary Search Partition Approach

1. Ensure the Smaller Array is Used for Binary Search:
   Let A = nums1 and B = nums2. If A is longer than B, swap them so that binary search is performed on the smaller array.

2. Determine the Total and Half Lengths:
   Let m be the length of A and n be the length of B.
   Total elements = m + n
   Half = (m + n) // 2

3. Binary Search Setup:
   Initialize two pointers, left and right, to perform binary search over A.

4. Partitioning the Arrays:

   • Choose an index i from A (using binary search), and calculate j = half - i for B.
   • Define:
     • Aleft = A[i-1] if i > 0, else -∞
     • Aright = A[i] if i < m, else +∞
     • Bleft = B[j-1] if j > 0, else -∞
     • Bright = B[j] if j < n, else +∞

5. Check for Correct Partition:
   The partition is valid if:

   • Aleft <= Bright and Bleft <= Aright
   • If valid:
     • If the total number of elements is odd, the median is min(Aright, Bright).
     • If even, the median is (max(Aleft, Bleft) + min(Aright, Bright)) / 2.
   • If not valid:
     • If Aleft > Bright, move the right pointer left.
     • Otherwise, move the left pointer right.

6. Return the Result:
   Once the correct partition is found, compute and return the median.

Python Code