Problem
Given two sorted arrays nums1 and nums2 of size m
and n
respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n))
.
Solution
Python3 Solution:
# this function will handle cases where array indices are out of range
def get_value_at_index(arr, i):
if i >= 0:
if i < len(arr):
return arr[i]
else:
return float("inf")
else:
return -float("inf")
class Solution:
def median_binary_search(self, nums1, nums2):
t = len(nums1) + len(nums2)
half = t // 2
start, end = 0, len(nums1) - 1
# since there will be a median value we can directly return the value
# hence keeping this while condition True
while True:
i = (start + end) // 2
j = half - (i + 1) - 1
if get_value_at_index(nums1, i) > get_value_at_index(nums2, j + 1):
end = i - 1
elif get_value_at_index(nums2, j) > get_value_at_index(nums1, i + 1):
start = i + 1
else:
if t % 2:
return min(
get_value_at_index(nums1, i + 1),
get_value_at_index(nums2, j + 1),
)
else:
return (
max(get_value_at_index(nums1, i), get_value_at_index(nums2, j))
+ min(
get_value_at_index(nums1, i + 1),
get_value_at_index(nums2, j + 1),
)
) / 2
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
return self.median_binary_search(nums1, nums2)
Test Cases
[1,3]
[2]
[1, 2, 3]
[3, 5, 6, 10]
[0, 19]
[1, 2]
[1, 2, 3, 4]
[3, 5, 6, 10]
[1, 2, 3, 4]
[3]
[1, 2, 3, 4]
[3, 4]
[1, 2, 10, 11]
[]
[]
[1]
[1, 2]
[]
[1, 2, 3]
[2]
[1, 3, 5, 5]
[4]