Median of two sorted arrays

break_it_down

• This problem can be solved usingbinary_search , another approach can be usingpriority_queue

• Solution usingbinary_search

class Solution:
    
    #Function to find the median of the two arrays when they get merged.
    def findMedianSortedArrays(self,A, n, B, m):
       
        n = len(A)
        m = len(B)
        if (n > m):
            return self.Median(B, A)  # Swapping to make A smaller
 
        start = 0
        end = n
        realmidinmergedarray = (n + m + 1) // 2
 
        while (start <= end):
            mid = (start + end) // 2
            leftAsize = mid
            leftBsize = realmidinmergedarray - mid
 
            # checking overflow of indices
            leftA = A[leftAsize - 1] if (leftAsize > 0) else float('-inf')
            leftB = B[leftBsize - 1] if (leftBsize > 0) else float('-inf')
            rightA = A[leftAsize] if (leftAsize < n) else float('inf')
            rightB = B[leftBsize] if (leftBsize < m) else float('inf')
 
            # if correct partition is done
            if leftA <= rightB and leftB <= rightA:
                if ((m + n) % 2 == 0):
                    return int((max(leftA, leftB) + min(rightA, rightB)) / 2.0)
                return int(max(leftA, leftB))
 
            elif (leftA > rightB):
                end = mid - 1
            else:
                start = mid + 1

Links

• https://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/