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.