A Hard binary search problem

Python Solution

class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m = len(nums1)
n = len(nums2)
if m > n:return self.findMedianSortedArrays(nums2, nums1)
l, r = 0, m
half = (n + m)//2
while l <= r:
i = (l + r) // 2
j = half - i
# magic to conquer the edge cases
max_left1 = -float('inf') if i == 0 else nums1[i - 1]
min_right1 = float('inf') if i == m else nums1[i]
max_left2 = -float('inf') if j == 0 else nums2[j - 1]
min_right2 = float('inf') if j == n else nums2[j]
if max_left1 > min_right2:
# i is too large
r = i - 1
continue
elif max_left2 > min_right1:
# i is too small
l = i + 1
continue
else:
# i is perfect
if (n + m) % 2 == 0:
return (max(max_left1, max_left2) + min(min_right1, min_right2))/2
else:
return min(min_right1, min_right2)

Thanks for reading.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi