# 9 lines O(log(min(m,n))) Python

• Same method as my 6-lines Ruby solution, just the binary search and the "get up to two" isn't quite as convenient in Python. See there if you'd like an explanation.

Solution 1

This one is a bit of a hack, as `bisect_left` is intended for lists, but apparently it's happy enough with something that behaves enough like a list (supports `__getitem__`):

``````def findMedianSortedArrays(self, nums1, nums2):
a, b = sorted((nums1, nums2), key=len)
m, n = len(a), len(b)
after = (m + n - 1) / 2
class Range:
def __getitem__(self, i):
return after-i-1 < 0 or a[i] >= b[after-i-1]
i = bisect.bisect_left(Range(), True, 0, m)
nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])
return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2.0
``````

Solution 2

Same, just with a self-made binary search:

``````def findMedianSortedArrays(self, nums1, nums2):
a, b = sorted((nums1, nums2), key=len)
m, n = len(a), len(b)
after = (m + n - 1) / 2
lo, hi = 0, m
while lo < hi:
i = (lo + hi) / 2
if after-i-1 < 0 or a[i] >= b[after-i-1]:
hi = i
else:
lo = i + 1
i = lo
nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])
return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2.0``````

• Here's my code based on your Solution 2, with some comments.

``````def findMedianSortedArrays(self, nums1, nums2):
a, b = sorted((nums1, nums2), key=len)
m, n = len(a), len(b)
after = (m + n - 1) / 2
# Determine i, j that a[0:i] + b[0:j] (exclusive) is the most small "after" numbers.
# There could multiple pairs of such (i, j) if there are some duplicated numbers.
# Each each such pair satisfies the following criteria at the same time:
# 1) i + j == after
# 2) (j>=1 and a[i] >= b[j-1]) or j==0
# 3) (i>=1 and b[j] >= a[i-1]) or i==0
lo, hi = 0, m
while lo < hi:
i = (lo + hi) / 2
j = after - i
cond1 = (j>=1 and a[i] >= b[j-1]) or j==0
cond2 = (i>=1 and b[j] >= a[i-1]) or i==0
if(cond1 and cond2):
lo = i
break
elif(not cond1):
assert(cond2)
lo = i + 1
else:
assert(cond1)
hi = i
i = lo
j = after - i
nextfew = sorted(a[i:i+2] + b[j:j+2])
return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2.0
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.