4. Median of Two Sorted Arrays (Array, Binary Search, Divide and Conquer)

링크 - https://leetcode.com/problems/median-of-two-sorted-arrays/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Hard

Intuition

1) Binary Search

 

class Solution:
    def findMedianSortedArrays(self, A: List[int], B: List[int]) -> float:
        na, nb = len(A), len(B)
        n = na + nb

        def solve(k, a_start, a_end, b_start, b_end):
            # If the segment of on array is empty, it means we have passed all
            # its element, just return the corresponding element in the other array.
            if a_start > a_end:
                return B[k - a_start]
            if b_start > b_end:
                return A[k - b_start]

            # Get the middle indexes and middle values of A and B.
            a_index, b_index = (a_start + a_end) // 2, (b_start + b_end) // 2
            a_value, b_value = A[a_index], B[b_index]

            # If k is in the right half of A + B, remove the smaller left half.
            if a_index + b_index < k:
                if a_value > b_value:
                    return solve(k, a_start, a_end, b_index + 1, b_end)
                else:
                    return solve(k, a_index + 1, a_end, b_start, b_end)
            # Otherwise, remove the larger right half.
            else:
                if a_value > b_value:
                    return solve(k, a_start, a_index - 1, b_start, b_end)
                else:
                    return solve(k, a_start, a_end, b_start, b_index - 1)

        if n % 2:
            return solve(n // 2, 0, na - 1, 0, nb - 1)
        else:
            return (
                solve(n // 2 - 1, 0, na - 1, 0, nb - 1)
                + solve(n // 2, 0, na - 1, 0, nb - 1)
            ) / 2

Time Complexity: O(log(m * n))

Space Complexity: O(1)

2) Better Binary Search

우리는 두개의 기준점을 사용할 것이다. 하나는 p1 = (left+right) // 2 이고 다른 하나는 p2 = (m+n+1)//2 - p2이다. 이 접근법의 기본 가정은 nums1의 길이가 nums2보다 작다는 점이다. 따라서 우리는 이 점을 이용하여 위의 두개의 기준점을 통해서 median을 찾아나간다.

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)

        m, n = len(nums1), len(nums2)
        left, right = 0, m

        while left <= right:
            p1 = (left + right) // 2
            p2 = (m + n + 1) // 2 - p1

            maxLeft1 = float('-inf') if p1 == 0 else nums1[p1-1]
            minRight1 = float('inf') if p1 == m else nums1[p1]
            maxLeft2 = float('-inf') if p2 == 0 else nums2[p2-1]
            minRight2 = float('inf') if p2 == n else nums2[p2]

            if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
                if (m+n) % 2 == 0:
                    return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2
                else:
                    return max(maxLeft1, maxLeft2)
            elif maxLeft1 > minRight2:
                right = p1 - 1
            else:
                left = p1 + 1

Time Complexity: O(log(min(m, n)))

Space Complexity: O(1)