***Median of Two Sorted Arrays (Leetcode 4)
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
A=nums1
B=nums2
if(len(A)>len(B)):
A,B=B,A
total=len(A)+len(B)
half=total//2
def bsearch(A,l,r):
Amid=(l+r)//2
Bmid=half-Amid-2
if(Amid>=0):
Aleft=A[Amid]
else:
Aleft=float('-inf')
if(Amid+1<len(A)):
Aright=A[Amid+1]
else:
Aright=float('inf')
if(Bmid>=0):
Bleft=B[Bmid]
else:
Bleft=float('-inf')
if(Bmid+1<len(B)):
Bright=B[Bmid+1]
else:
Bright=float('inf')
if(Aleft<=Bright and Bleft<=Aright):
# Odd case
if(total%2==1):
return min(Aright,Bright)
# Even case
else:
return (max(Aleft,Bleft)+min(Aright,Bright))/2
elif(Aleft>Bright):
return bsearch(A,l,Amid-1)
else:
return bsearch(A,Amid+1,r)
return bsearch(A,0,len(A)-1)
PreviousSingle Element in a Sorted Array (Leetcode 540)NextCount Negative Numbers in a Sorted Matrix (Leetcode 1351)
Last updated