← DiffPush

Median of two sorted arrays

Baseline Binary Search · In Search Space O(log(min(m, n))) · O(1)

Splitting Two Merged Shift Rosters at the Median

Two facilities each keep a sorted roster of shift durations, and planners must find the median duration across both rosters combined - without actually concatenating them. The trick is to cut both rosters at complementary positions so the left cut holds exactly half of all entries with every left entry at most every right entry.

Input: Two sorted arrays nums1 and nums2 of sizes m and n.

Output: The median of the combined sorted values, as a double (averaged middle pair when the total count is even).

Constraints

• 0 <= m, n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6
• An O(log(m + n)) algorithm is required

Examples

Example 1

Input: {"nums1":[1,3],"nums2":[2]}
Output: 2
The combined order 1, 2, 3 has a single middle value, 2.

Example 2

Input: {"nums1":[1,2],"nums2":[3,4]}
Output: 2.5
With an even total, the median averages the two middle values, 2 and 3.

Solve this in your browser →

Also on LeetCode ↗