Python Code To Find Median of Sorted Arrays of Equal Size

The following code has two implementations of finding median of two sorted arrays in O(n) and O(log n).

# Program to find median of two sorted arrays
def findMedianFaster(arr_a, arr_b, start_a, end_a, start_b, end_b):
# first base case of both arrays having 2 elements
if (end_a - start_a) == 1 and (end_b - start_b) == 1:
m1 = max(arr_a[start_a], arr_b[start_b])
m2 = min(arr_a[end_a], arr_b[end_b])
return (m1+m2)/2
# Second base case
# Medians are equal in both the arrays
m1_idx = (end_a + start_a)/2
m2_idx = (end_b + start_b)/2
m1 = arr_a[m1_idx]
m2 = arr_b[m2_idx]
print("m1={} m2={}".format(m1, m2))
if m1 == m2:
return m2
if m1 < m2:
start_a = m1_idx
end_b = m2_idx
if m2 < m1:
start_b = m2_idx
end_a = m1_idx
print("start_a={} end_a={} start_b={} end_b={}".format(start_a, end_a, start_b, end_b))
return findMedianFaster(arr_a, arr_b, start_a, end_a, start_b, end_b)
# O(n) method of finding median
def findMedian(arr1, arr2):
len1 = len(arr1)
len2 = len(arr2)
i = 0
j = 0
count = 0
m1 = 0
m2 = 0
# Perform the merge phase of mergesort
while 1:
if i == len1:
m1 = m2
m2 = arr2[0]
break
if j == len2:
m1 = m2
m2 = arr2[1]
break
if count == (len1 + len2) /2:
break
if arr1[i] < arr2[j]:
count += 1
m1 = m2
m2= arr1[i]
i += 1
elif arr2[j] < arr1[i]:
count += 1
m1 = m2
m2= arr2[j]
j += 1
print("m1={} m2={}".format(m1, m2))
return m1, m2
arr1 = [1, 2, 3, 4, 5]
arr2 = [4, 7, 11, 12, 100]
print(findMedian(arr1, arr2))
print(findMedianFaster(arr1, arr2, 0, 4, 0, 4))

Reference

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: