Problem statement

https://binarysearch.com/problems/Median-of-Two-Sorted-Lists/

Solution

Equal to Leetcode 0004 Median of Two Sorted Arrays. Be careful about definition of median, it is different here. Here is a bit different implementation.

Complexity

It is O(log(m + n)) for time and O(1) for additional space.

Code

class Solution:
    def solve(self, A, B):
        n, m = len(A), len(B)
        if n > m: A, B, n, m = B, A, m, n

        k = n + m >> 1
        lo, hi = 0, n
        while lo < hi:
            mid = hi + lo >> 1
            if B[k - mid - 1] > A[mid]:
                lo = mid + 1
            else:
                hi = mid

        if lo >= n: return B[k - lo]
        if k - lo >= m: return A[lo]
        return min(A[lo], B[k - lo])