Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Merging the two arrays with two pointers gives an O(n + m) solution — you only need to walk to the middle.
  2. 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