[Leetcode/Binary Search] 4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/description/

 

---

🔹 문제 풀이 접근

이 문제는 두 개의 정렬된 배열(nums1, nums2)이 주어질 때, 병합 후 중앙값(median)을 찾는 문제이다.

 

✅ 최적화 방법 (이진 탐색 활용)

• 이진 탐색(Binary Search)을 사용하여 한 배열을 절반으로 분할하면서 답을 찾음.
• 시간 복잡도: O(log(min(m, n)))

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # nums1이 항상 짧은 배열이 되도록 보장
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        
        x, y = len(nums1), len(nums2)
        low, high = 0, x
        
        while low <= high:
            partitionX = (low + high) // 2
            partitionY = (x + y + 1) // 2 - partitionX
            
            # 왼쪽 파티션의 최대값
            maxX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
            maxY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
            
            # 오른쪽 파티션의 최소값
            minX = float('inf') if partitionX == x else nums1[partitionX]
            minY = float('inf') if partitionY == y else nums2[partitionY]
            
            if maxX <= minY and maxY <= minX:
                # 배열의 전체 길이가 짝수인 경우
                if (x + y) % 2 == 0:
                    return (max(maxX, maxY) + min(minX, minY)) / 2
                else:
                    return max(maxX, maxY)
            
            elif maxX > minY:
                high = partitionX - 1  # 왼쪽으로 이동
            else:
                low = partitionX + 1  # 오른쪽으로 이동

🔹 알고리즘 설명 (Binary Search)

1. nums1을 항상 짧은 배열로 설정
   • nums1이 nums2보다 길면 swap → 이진 탐색 범위를 최소화.
2. 이진 탐색 수행
   • partitionX: nums1을 절반으로 나누는 위치.
   • partitionY: nums2를 나누는 위치 ((x + y + 1) // 2 - partitionX).
3. 왼쪽/오른쪽 파티션 값 구하기
   • maxX: nums1 왼쪽 부분 최대값.
   • maxY: nums2 왼쪽 부분 최대값.
   • minX: nums1 오른쪽 부분 최소값.
   • minY: nums2 오른쪽 부분 최소값.
4. 조건 검사
   • maxX ≤ minY AND maxY ≤ minX → 중앙값 찾음.
   • (x + y) % 2 == 0: 짝수 개 → (max(left) + min(right)) / 2
   • 홀수 개 → max(left)
   • maxX > minY → high = partitionX - 1 (왼쪽 이동).
   • maxY > minX → low = partitionX + 1 (오른쪽 이동).

🔹 시간 복잡도 분석

• 이진 탐색 사용 → O(log(min(m, n)))
• 최종 시간 복잡도: O(log(min(m, n)))
• 공간 복잡도: O(1) (추가 공간 사용 없음)