Median of Two Sorted Arrays

Hard · Binary Search

You are given two integer arrays, each already sorted in non-decreasing order. Imagine merging them into one sorted array without actually building it, and return the median value of that combined array. If the merged array has an even number of elements the median is the average of its two middle elements, otherwise it is the single middle element. Return the result as a float.

Examples

Input:  nums1 = [1,3], nums2 = [2]
Output: 2.0
Why:    Merging gives [1,2,3], whose middle value is 2.

Input:  nums1 = [1,2], nums2 = [3,4]
Output: 2.5
Why:    Merging gives [1,2,3,4], the average of the two middle values 2 and 3 is 2.5.

Input:  nums1 = [], nums2 = [1]
Output: 1.0
Why:    The second array alone supplies the only element, which is the median.

Constraints

0 <= nums1.length, nums2.length <= 10^4, 1 <= nums1.length + nums2.length <= 10^4, both arrays sorted in non-decreasing order, -10^6 <= nums1[i], nums2[i] <= 10^6

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Median of Two Sorted Arrays

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Median of Two Sorted Arrays. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.