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
- https://www.youtube.com/watch?v=MHNTl_NvOj0
The most lucid explanation of the code.
