Median of two sorted arrays

Question

The task is to find the median of two Arrays. I have an O(n) solution. Can it be written in a better time complexity?

def findMedianSortedArrays(self, A, B):
 combined = []
 while len(A) > 0 and len(B) > 0:
 if (A[0] < B[0]):
 combined.append(A.pop(0))
 else:
 combined.append(B.pop(0))
 combined.extend(A)
 combined.extend(B)
 length = len(combined)
 if length % 2 != 0:
 return combined[length // 2]
 else:
 return (combined[length // 2-1] + combined[length//2]) / 2

Answer 1

According to the Style Guide for Python Code, function and variable names should be "lowercase, with words separated by underscores as necessary to improve readability." In your case I'd suggest

def median_of_sorted_arrays(a, b):

Your code determines the median correctly. However, it modifies the passed arguments, which might be unexpected to the caller:

a = [-5, 3, 6, 12, 15]
b = [-12, -10, -6, -3, 4, 10]
print(findMedianSortedArrays(a, b)) # prints 3
print(findMedianSortedArrays(a, b)) # prints 13.5

This could be fixed by accessing the lists via subscripting:

i = 0
j = 0
while i < len(a) and j < len(b):
 if (a[i] < b[j]):
 combined.append(a[i])
 i += 1
 else:
 combined.append(b[j])
 j += 1
combined.extend(a[i:])
combined.extend(b[j:])

The next possible improvement is to get rid of the additional storage: Instead of storing elements from a or b into the combined list you could just count how many elements have been merged so far, until the median element is found.

A more efficient algorithm is described in

• Median of two sorted arrays with different sizes in O(log(min(n, m)))

The basic idea is to partition both a and b into

a[:i] + a[i:]
b[:j] + b[j:]

such that the following conditions are satisfied:

i + j = (len(a) + len(b) + 1) // 2
a[i-1] <= b[j]
b[j-1] <= a[i]

and this can be done efficiently with a binary search. Then the "union" of the first (resp. second) halves is the first (resp. second) half of the combined array, so that the median is

max(a[i - 1], b[j - 1]) # if the total length is odd
(max(a[i - 1], b[j - 1]) + min(a[i], b[j])) / 2 # if the total length is even