Created
November 4, 2016 11:35
-
-
Save thehoneymad/d69553f246324f9bc1f38e8c1312411f to your computer and use it in GitHub Desktop.
Get median of two sorted same sized array
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # Im trying with same sized array here | |
| array1 = [10,11,12,18,20] | |
| array2 = [2,5,8,15,19] | |
| def GetMedianOfTwoArrays(array1, array2, a1Start, a1End, a2Start, a2End): | |
| # Find medians from the two arrays | |
| m1 = (a1Start + a1End) / 2 | |
| m2 = (a2Start + a2End) / 2 | |
| if (a1End - a1Start == 1 & a2End - a2Start == 1): | |
| # if we have two 2 sized sorted array here then the median is max(array1[0], array2[0]) + min(array1[1], array2[1]) / 2 | |
| return (max(array1[a1Start], array2[a2Start]) + min(array1[a1End], array2[a2End])) / 2 | |
| if (array1[m1] == array2[m2]): | |
| return array1[m1] | |
| if (array1[m1] > array2[m2]): | |
| # This essentially means that I have to look from array1Start to mid1 and mid2 to array2End | |
| return GetMedianOfTwoArrays(array1, array2, a1Start, m1, m2, a2End) | |
| else: | |
| # This essentially means that I have to look for mid1 to array1End and array2Start to mid2 | |
| return GetMedianOfTwoArrays(array1, array2, m1, a1End, a2Start, m2) | |
| result = GetMedianOfTwoArrays(array1, array2, 0,len(array1)-1, 0, len(array2)-1) | |
| print(result) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment