# Question

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0


Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5


# Solution

Note, in the analysis the indexes start at 1, while in Python it starts at 0. Thus // produces the first index in the larger half.

class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
if len(nums1) >= len(nums2):
b = nums1
a = nums2
else:
b = nums2
a = nums1

m = len(a)
n = len(b)
if m == 0:
if n == 0:
raise ValueError
elif n % 2 == 0:
return (b[n // 2] + b[n // 2 - 1]) / 2
else:
return b[n // 2]

imin = 0
imax = m
half_len = (m + n + 1) // 2
while imin <= imax:
i = (imin + imax) // 2
j = half_len - i

if i > 0 and j < n and a[i-1] > b[j]: # i too big
imax = i - 1
elif j > 0 and i < m and b[j-1] > a[i]: # i too small
imin = i + 1
else:
if i == 0: max_of_left = b[j-1]
elif j == 0: max_of_left = a[i-1]
else: max_of_left = max(a[i-1], b[j-1])

if (m + n) % 2 == 1:
return max_of_left

if i == m: min_of_right = b[j]
elif j == n: min_of_right = a[i]
else: min_of_right = min(a[i], b[j])

return (max_of_left + min_of_right) / 2.0


# Analysis

See original post here.