Practice › Binary Search
Median of Two Sorted Arrays
Hard · Binary Search · Asked at Google, Amazon, Microsoft, Goldman Sachs, Adobe
Find the median of the combined values of two sorted arrays. Print it with exactly one digit after the decimal point (e.g. 2.0 or 2.5).
Input
Line 1: n. Line 2: n integers. Line 3: m. Line 4: m integers.
Output
The median with one decimal digit.
Constraints
- 1 ≤ n, m ≤ 10^5
- -10^6 ≤ values ≤ 10^6
An O(log(min(n, m))) partition-based binary search exists, but merging is O(n + m) and also accepted.
Example 1
Input
2 1 3 1 2
Output
2.0
Example 2
Input
2 1 2 2 3 4
Output
2.5
Hints
- Merging the two arrays with two pointers gives an O(n + m) solution — you only need to walk to the middle.
- Optimal: binary search a cut in the smaller array so that everything left of both cuts ≤ everything right of them.
Approach
The total is t = n + m. The median is the element at index t / 2 when t is odd, or the average of indices t/2 − 1 and t/2 when it's even. Merge with two pointers and stop once you reach index t/2. That's O(n + m) and fast enough here. The O(log min(n, m)) version binary searches how many elements the smaller array contributes to the left half. Print with one decimal: the median is always a whole number or ends in .5.
Complexity: O(n + m) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
cin >> m;
vector<long long> b(m);
for (auto &x : b) cin >> x;
int t = n + m, i = 0, j = 0;
long long prev = 0, cur = 0;
for (int k = 0; k <= t / 2; k++) {
prev = cur;
if (j >= m || (i < n && a[i] <= b[j])) cur = a[i++];
else cur = b[j++];
}
double median = (t % 2 == 1) ? cur : (prev + cur) / 2.0;
printf("%.1f\n", median);
return 0;
}Python solution
import sys
from heapq import merge
from itertools import islice
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a = data[1 : n + 1]
m = data[n + 1]
b = data[n + 2 : n + 2 + m]
t = n + m
middle = list(islice(merge(a, b), t // 2 + 1))[-2:]
median = middle[-1] if t % 2 else (middle[0] + middle[1]) / 2
print(f"{median:.1f}")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
int m = sc.nextInt();
long[] b = new long[m];
for (int i = 0; i < m; i++) b[i] = sc.nextLong();
int t = n + m, i = 0, j = 0;
long prev = 0, cur = 0;
for (int k = 0; k <= t / 2; k++) {
prev = cur;
if (j >= m || (i < n && a[i] <= b[j])) cur = a[i++];
else cur = b[j++];
}
double median = (t % 2 == 1) ? cur : (prev + cur) / 2.0;
System.out.println(String.format(Locale.US, "%.1f", median));
}
}Solve Median of Two Sorted Arrays online · All practice problems