Fork me on GitHub

Median of Two Sorted Arrays

Posted on

Description

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:

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

The median is 2.0

Example 2:

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        INF = 100000000000
        self.len1 = len(nums1)
        self.len2 = len(nums2)
        if self.len1 == 0:
            return nums2[self.len2/2] if self.len2 % 2 else float(nums2[int(self.len2/2)-1] + nums2[int(self.len2/2)])/2 
        if self.len2 == 0:
             return nums1[self.len1/2] if self.len1 % 2 else float((nums1[int(self.len1/2)-1] + nums1[int(self.len1/2)]))/2
        
        median_index_1 = int((self.len1 - 1) / 2) 
        median_index_2 = int( (self.len1 + self.len2 + 1)/2 ) - (median_index_1+1) - 1
        
        while True:
            left_1 = -INF if median_index_1 < 0 else nums1[median_index_1] 
            right_1 = INF if median_index_1+1 >= self.len1 else nums1[median_index_1+1]
            left_2 = -INF if median_index_2 < 0 else nums2[median_index_2]
            right_2 = INF if median_index_2+1 >= self.len2 else nums2[median_index_2+1]
            if left_1 <= right_2 and left_2 <= right_1:
                if (self.len1 + self.len2) % 2 == 0:
                    print(left_1, left_2, right_1, right_2)
                    return float( max(left_1, left_2) + min(right_1, right_2) ) / 2
                else:
                    ##Since the number of left part is larger than or equal to right part
                    return max(left_1, left_2)

            if left_1 > right_2:
                median_index_1 -= 1
                median_index_2 += 1
                continue

            if left_2 > right_1:
                median_index_1 += 1
                median_index_2 -= 1
                continue

####

Remains to Do

How to prove the time scale is log(m+n)