Problem statement

https://leetcode.com/problems/median-of-two-sorted-arrays/

Solution

The idea is similar to binary search: we need to find element $i$ such that: $\text{B}[j-1] \leq \text{A}[i]$ and $\text{A}[i-1] \leq \text{B}[j]$, where $j = \frac{m + n + 1}{2} - i$ However it is more easily to say this than to be done.

Complexity

Time complexity is $O(\log (m+n))$, space complexity is $O(1)$.

Code

class Solution:
    def findMedianSortedArrays(self, A, B):
        if len(A) > len(B): A, B = B, A
        n1, n2 = len(A), len(B)
        
        beg, end = 0, n1
        while beg <= end:
            mid1 = (beg + end)//2
            mid2 = (n1 + n2)//2 - mid1
            
            l1 = -float("inf") if mid1 == 0 else A[mid1-1]
            l2 = -float("inf") if mid2 == 0 else B[mid2-1]
            r1 =  float("inf") if mid1 == n1 else A[mid1]
            r2 =  float("inf") if mid2 == n2 else B[mid2]
            
            if l1 > r2:
                end = mid1 - 1
            elif l2 > r1:
                beg = mid1 + 1
            else:
                return min(r1, r2) if (n1+n2)%2 else (max(l1,l2) + min(r1,r2))/2

Remark

I do not really like solution still, I think code can be improved.