LeetCode Q4: Median of Two Sorted Arrays

Problem

You are given two sorted arrays nums1 and nums2 of size m and n respectively, and you need to find the median of the two sorted arrays. The overall run-time complexity should be O(log(min(m, n))).

Example:

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

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

Want a deeper dive into the solution? Watch the full video tutorial:

Recommended Data Structure and Algorithm

To tackle this problem efficiently, we use binary search on the smaller of the two arrays to maintain the time complexity constraint of O(log(min(m, n))). Binary search helps locate the partition points in both arrays, enabling an efficient calculation of the median.

Solution

Logic

1. Perform binary search on the smaller of the two arrays, a, to optimize the search space.
2. Partition aat splitA and b at splitB such that both left halves contain as many elements as both right…