I've written a solution to the leetcode problem Median of Two Sorted arrays. The solution I anticipated coming up with initially was going to features some kind of binary search on both arrays based on the range of numbers (given that the question calls for a runtime of O(log (m+n))).
Along the way, I thought of another, simpler solution that featured averaging the largest number of both arrays (the last element of one of the arrays) and the smallest number of the two arrays (index 0 of one of the arrays). I also include a number of if statements to handle the possible different array lengths that could be passed in. I'm particularly interested in the approach of this solution since it would have a faster runtime than what was suggested.
This solution surprisingly passes 2056 / 2084 of the test cases. It fails, however, on the input arrays of
,[-2,-1], which leads me to believe that the code will fail only when there exist negative numbers in either array. Is this the case, or is it just that the test cases used for the question aren't wide-ranging enough?
class Solution: def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ if len(nums1) == 0 and len(nums2) == 0: return None if len(nums1) == 0 and len(nums2) > 0: if len(nums2) == 1: return nums2 elif len(nums2) > 1 and len(nums2) % 2 == 1: lo,hi = 0,len(nums2)-1 mid = (hi+lo)//2 return nums2[mid] elif len(nums2) > 1 and len(nums2) % 2 == 0: lo,hi = 0,len(nums2)-1 mid = (hi+lo)//2 return (nums2[mid] + nums2[mid+1])/2 if len(nums1) > 0 and len(nums2) == 0: if len(nums1) == 1: return nums1 elif len(nums1) > 1 and len(nums1) % 2 == 1: lo,hi = 0,len(nums1)-1 mid = (hi+lo)//2 return nums1[mid] elif len(nums1) > 1 and len(nums1) % 2 == 0: lo,hi = 0,len(nums1)-1 mid = (hi+lo)//2 return (nums1[mid] + nums1[mid+1])/2 l1A,l2A,l1B,l2B = 0,0,len(nums1)-1,len(nums2)-1 arrBeg = nums1[l1A] if nums1[l1A] <nums2[l2A] else nums2[l2A] arrEnd = nums1[l1B] if nums1[l1B] > nums2[l2B] else nums2[l2B] target = (arrEnd+arrBeg)/2 return target