Median of Two Sorted Arrays

HardBinary Search

Asked byAmazonAdobeGoldman SachsMicrosoftAppleGoogle

Problem

Given two sorted arrays, return the median of the combined data set, in O(log(m+n)) time.

Examples

Example 1

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

Output:2.0

Example 2

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

Output:2.5

Constraints

0 <= m, n
At least one of the two arrays is non-empty.

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Binary Search pattern

Repeatedly halve the search space by comparing the middle element to a target, turning an O(n) scan into O(log n). It works on more than sorted arrays — any "answer space" that's monotonic (true…true…false…false) can be binary searched.

Look for this pattern when

The input is sorted, or partially sorted (like a rotated sorted array).
You're minimizing or maximizing a value where "is X feasible?" is easy to check and feasibility is monotonic.

Read the full Binary Search guide →

Video walkthroughs

Original problem on LeetCode ↗