# 20+ python codes in O(log(mn)) with detail analysis

• It is the 4th problem I wrote in leetcode, and it took me a long time to figure out the solution.

I wrote it in 20+ lines python and detail analysis and code are provided on github, very easy to understand.

I bet you will love my solution ;))

``````class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
def _search(l1, l2, k):
if len(l1) == 0:
return l2[k]
if len(l2) == 0:
return l1[k]
if k == 0:
return min(l1[0], l2[0])
mid1 = len(l1) >> 1
mid2 = len(l2) >> 1
if mid1 + mid2 < k:
if l1[mid1] > l2[mid2]:
return _search(l1, l2[mid2+1:], k - mid2 - 1)
else:
return _search(l1[mid1+1:], l2, k - mid1 - 1)
else:
if l1[mid1] > l2[mid2]:
return _search(l1[:mid1], l2, k)
else:
return _search(l1, l2[:mid2], k)
totalLen = len(nums1) + len(nums2)
if totalLen % 2 == 0:
return (_search(nums1, nums2, totalLen >> 1) + _search(nums1, nums2, (totalLen >> 1) - 1)) / 2.0
else:
return _search(nums1, nums2, totalLen >> 1)
``````

And I wrote a markdown file on github, which explains the algorithm in great details:

my analysis

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