# 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 break if j == len2: m1 = m2 m2 = arr2 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

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