Median of Two Sorted Arrays

Problem

Return the median of two sorted lists a and b as a float in O(log(min(len(a), len(b)))) time.

Binary search a partition of the shorter list so the left halves together hold (m + n + 1) // 2 elements and every left value is at most every right value. For an odd total return the largest left value, otherwise the average of the largest left and the smallest right.

Hint

Swap so the shorter list is partitioned; sentinels handle empty left or right sides.

Test cases

case 1

in: [[1,3],[2]]

expected: 2

case 2

in: [[1,2],[3,4]]

expected: 2.5

case 3

in: [[],[1]]

expected: 1

case 4

in: [[0,0],[0,0]]

expected: 0

case 5

in: [[2],[]]

expected: 2

Starter codePython

def find_median_sorted(a, b):
    # Your code here
    pass

5 test cases · run your code against them in the editor