Exp.binary searcharrays

Median of Two Sorted Arrays

Find the median of two sorted arrays without merging them.

Two arrays a and b are each sorted ascending. Return the median of the two combined.

With an even total length the median is the mean of the two middle values, so the answer can be a half-integer — the return type is a float and the grader compares with a tolerance.

At least one of the arrays is non-empty.

Constraints

  • 0 ≤ a.length, b.length ≤ 100,000
  • 1 ≤ a.length + b.length
  • -10⁹ ≤ values ≤ 10⁹

If you're a true master, try it in O(log(m + n)) time

Examples

Input
a = [1,3], b = [2]
Output
2
Why
Odd total, so the middle value itself.
Input
a = [1,2], b = [3,4]
Output
2.5
Why
Even total: the mean of 2 and 3.
Input
a = [], b = [1]
Output
1
Why
One array may be empty.

Submitting also runs 8 hidden tests.

Limits

2000 ms and 256 MB per test case.

You can run the examples without an account. Sign in to submit against the hidden cases and keep your progress.

Run checks the examples above. Submit checks those plus the hidden cases.