← 전체 회차
A-034● Day 342026.06.09hardleetcode #4neetcode150

두 정렬 배열의 중앙값

#array#binary-search#divide-and-conquer
↗ leetcode #4 · median-of-two-sorted-arrays
01

문제

· problem
P.034

두 정렬 배열의 중앙값

↗ leetcode #4

크기가 각각 m과 n인 두 개의 정렬된 배열 nums1과 nums2가 주어질 때, 두 배열의 중앙값을 반환하세요. 전체 실행 시간 복잡도는 O(log (m+n))이어야 합니다.

제약
  • · 0 ≤ m ≤ 1000, 0 ≤ n ≤ 1000
  • · 1 ≤ m + n ≤ 2000
  • · -10^6 ≤ nums1[i], nums2[i] ≤ 10^6
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[1,3]
[2]
2.00000
example 2input → output
[1,2]
[3,4]
2.50000
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    중앙값(median)은 정확히 무엇을 의미하나요?
  • ☐
    배열 중 하나 또는 둘 다 비어있을 수 있나요?
  • ☐
    왜 시간 복잡도가 O(log(m+n))이어야 하나요?
  • ☐
    배열이 음수를 포함할 수 있나요?
  • ☐
    중복된 값이 있을 수 있나요?
  • ☐
    중앙값이 항상 정수인가요?
  • ☐
    두 배열을 항상 그대로 사용해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 총 길이와 목표 위치 계산
○
total = len(nums1) + len(nums2)
○
total = len(nums1) + len(nums2) + 1
○
total = max(len(nums1), len(nums2))
step 2· 더 작은 배열 선택
○
if len(B) < len(A):
○
if len(A) < len(B): A, B = B, A
○
A, B = B, A
step 3· 이진 탐색 범위 초기화
○
l, r = 0, len(A) - 1
○
l, r = 0, len(B) - 1
○
l, r = 0, half
step 4· 배열 B의 분할점 계산│ 중첩
○
j = half - i - 2  # B
○
j = half - i - 1
○
j = half - i
step 5· 분할점의 경계값 추출│ 중첩
○
Aleft = A[i] if i >= 0 else float("-infinity")
○
Aleft = A[i] if i >= 0 else float('infinity')
○
Aleft = A[i - 1] if i > 0 else float('-infinity')
step 6· 분할의 유효성 검증│ 중첩
○
if Aleft <= Bright and Bleft <= Aright:
○
if Aleft <= Bright or Bleft <= Aright:
○
if Aleft < Bright and Bleft < Aright:
step 7· 이진 탐색 범위 조정│ 중첩
○
elif Aleft > Bright:
○
elif Aleft < Bright: r = i - 1
○
elif Aleft > Bright: l = i + 1
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
# Time: log(min(n, m))
2
3
4
class Solution:
5
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
6
        A, B = nums1, nums2
7
        total = len(nums1) + len(nums2)
8
        half = total // 2
9
10
        if len(B) < len(A):
11
            A, B = B, A
12
13
        l, r = 0, len(A) - 1
14
        while True:
15
            i = (l + r) // 2  # A
16
            j = half - i - 2  # B
17
18
            Aleft = A[i] if i >= 0 else float("-infinity")
19
            Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
20
            Bleft = B[j] if j >= 0 else float("-infinity")
21
            Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")
22
23
            # partition is correct
24
            if Aleft <= Bright and Bleft <= Aright:
25
                # odd
26
                if total % 2:
27
                    return min(Aright, Bright)
28
                # even
29
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
30
            elif Aleft > Bright:
31
                r = i - 1
32
            else:
33
                l = i + 1
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[1,3]
[2]
→
2.00000
case 2
[1,2]
[3,4]
→
2.50000
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.