Median of Two Sorted Arrays

The problem

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Function: def findMedianSortedArrays(a,b):

Example input (a JSON list of arguments): [[1, 3], [2]]
Expected output: 2.0

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. Binary-search the partition in the shorter sorted array until both left sides are no larger than the opposite right sides.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def findMedianSortedArrays(a,b):
    if len(a)>len(b): return findMedianSortedArrays(b,a)
    m,n=len(a),len(b); lo,hi=0,m
    while lo<=hi:
        i=(lo+hi)//2; j=(m+n+1)//2-i
        al=a[i-1] if i else -float('inf'); ar=a[i] if i<m else float('inf')
        bl=b[j-1] if j else -float('inf'); br=b[j] if j<n else float('inf')
        if al<=br and bl<=ar: return float(max(al,bl)) if (m+n)%2 else (max(al,bl)+min(ar,br))/2
        if al>br: hi=i-1
        else: lo=i+1

Why it works

Binary-search the partition in the shorter sorted array until both left sides are no larger than the opposite right sides. Read the middle one or two boundary values; the combined input is nonempty.

Complexity: O(log min(m,n)) time / O(1) space.

Time: O(log min(m,n)) time · Space: O(1) space