-
-
Save Petelin/d6cffbaf71931a7852a3889bb80a926c to your computer and use it in GitHub Desktop.
leetcode 4.Median of Two Sorted Arrays
This file contains 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
def median(A, B): | |
m, n = len(A), len(B) | |
if m > n: | |
A, B, m, n = B, A, n, m | |
if n == 0: | |
raise ValueError | |
imin, imax, half_len = 0, m, (m + n + 1) / 2 | |
while imin <= imax: | |
i = (imin + imax) / 2 | |
j = half_len - i | |
if i < m and B[j-1] > A[i]: | |
# i is too small, must increase it | |
imin = i + 1 | |
elif i > 0 and A[i-1] > B[j]: | |
# i is too big, must decrease it | |
imax = i - 1 | |
else: | |
# i is perfect | |
if i == 0: max_of_left = B[j-1] | |
elif j == 0: max_of_left = A[i-1] | |
else: max_of_left = max(A[i-1], B[j-1]) | |
if (m + n) % 2 == 1: | |
return max_of_left | |
if i == m: min_of_right = B[j] | |
elif j == n: min_of_right = A[i] | |
else: min_of_right = min(A[i], B[j]) | |
return (max_of_left + min_of_right) / 2.0 |
Author
Petelin
commented
Jan 6, 2020
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment