정렬된 두 배열의 중앙값
더 짧은 배열의 분할 경계에 이진 탐색을 적용해 O(log(min(m,n))) 시간에 두 정렬 배열의 중앙값을 구합니다.
정렬된 두 배열의 중앙값은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
정렬된 두 배열의 중앙값
정렬된 두 배열의 중앙값 (LeetCode 4)은 대표적인 어려운 문제입니다. 정렬된 두 배열 nums1(길이 m)과 nums2(길이 n)가 주어졌을 때, 두 배열을 합쳐 정렬한 수열의 중앙값을 O(log(min(m,n))) time에 찾습니다. 단순한 접근법은 두 배열을 O(m+n)에 병합하지만, 최적 해법은 분할 경계에 이진 탐색을 적용합니다. 이 문제는 주요 기술 기업의 면접에서 가장 자주 출제되는 어려운 문제 중 하나입니다.
# Examples:
nums1 = [1, 3]
nums2 = [2]
# Combined sorted: [1, 2, 3] → median = 2.0
nums1b = [1, 2]
nums2b = [3, 4]
# Combined sorted: [1, 2, 3, 4] → median = (2+3)/2 = 2.5
print('Example 1 median:', 2.0)
print('Example 2 median:', 2.5)
print('Total length:', len(nums1)+len(nums2), 'and', len(nums1b)+len(nums2b))단순 병합 접근법
가장 단순한 O(m+n) 접근법은 두 정렬 배열을 병합한 다음 중앙값을 찾는 것입니다. 두 정렬 배열을 병합하는 데는 O(m+n)이 걸립니다. 길이가 L인 배열의 중앙값은 L이 홀수이면 arr[L//2]이고, 짝수이면 (arr[L//2-1] + arr[L//2]) / 2입니다. 이 방법은 정확하지만 O(log(min(m,n))) 요구 사항을 충족하지 못합니다. 면접에서는 기준점을 세우기 위해 항상 이 방법을 먼저 제시한 다음 최적화하십시오.
def find_median_naive(nums1, nums2):
# Merge two sorted arrays
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i]); i += 1
else:
merged.append(nums2[j]); j += 1
merged += nums1[i:] + nums2[j:]
L = len(merged)
if L % 2 == 1:
return float(merged[L // 2])
return (merged[L//2 - 1] + merged[L//2]) / 2.0
print(find_median_naive([1,3],[2])) # 2.0
print(find_median_naive([1,2],[3,4])) # 2.5분할 아이디어
핵심 통찰은 중앙값이 합쳐진 배열을 크기가 같은 두 절반으로 나눈다는 것입니다. 다음 조건을 만족하도록 nums1의 분할과 nums2의 분할을 찾아야 합니다. (1) 왼쪽 절반의 전체 크기와 오른쪽 절반의 전체 크기가 같습니다. (2) 왼쪽 절반의 모든 원소가 오른쪽 절반의 모든 원소보다 작거나 같습니다. nums1에서 올바른 분할 지점을 이진 탐색하면 전체 길이 조건에 따라 nums2의 분할 지점은 자동으로 결정됩니다.
# Partition concept visualised:
# nums1: [1, 3] | [5, 7] (partition after index 1)
# nums2: [2, 4] | [6, 8] (partition after index 1)
# Combined left: [1, 3, 2, 4] = 4 elements
# Combined right: [5, 7, 6, 8] = 4 elements
# Valid if max(left) <= min(right): max(3,4)=4 <= min(5,6)=5 ✓
# Median = (max_left + min_right) / 2 = (4+5)/2 = 4.5
nums1, nums2 = [1,3,5,7], [2,4,6,8]
merged = sorted(nums1+nums2)
print('Merged:', merged)
L = len(merged)
print('Median:', (merged[L//2-1]+merged[L//2])/2 if L%2==0 else merged[L//2])분할에 대한 이진 탐색
더 짧은 배열인 nums1의 분할 인덱스 i를 이진 탐색합니다. nums2의 분할 인덱스 j는 j = (m+n+1)//2 - i로 결정됩니다(왼쪽 절반에 (m+n+1)//2개의 원소가 있도록 함). 분할은 nums1[i-1] ≤ nums2[j]이고 nums2[j-1] ≤ nums1[i]일 때 유효합니다. 이 균형을 찾을 때까지 이진 탐색으로 i를 증가시키거나 감소시킵니다.
def find_median_sorted_arrays(nums1, nums2):
# Ensure nums1 is the shorter array
if len(nums1) > len(nums2):
return find_median_sorted_arrays(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # partition index in nums1
j = (m + n + 1) // 2 - i # partition index in nums2
# Boundary values with sentinels
max_left1 = float('-inf') if i == 0 else nums1[i-1]
min_right1 = float('inf') if i == m else nums1[i]
max_left2 = float('-inf') if j == 0 else nums2[j-1]
min_right2 = float('inf') if j == n else nums2[j]
if max_left1 <= min_right2 and max_left2 <= min_right1:
# Found the correct partition
if (m + n) % 2 == 1:
return float(max(max_left1, max_left2))
return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2.0
elif max_left1 > min_right2:
hi = i - 1 # i is too large, move left
else:
lo = i + 1 # i is too small, move right
return 0.0
print(find_median_sorted_arrays([1,3],[2])) # 2.0
print(find_median_sorted_arrays([1,2],[3,4])) # 2.5이진 탐색 추적
nums1=[1,3], nums2=[2]를 추적해 보겠습니다. m=2, n=1, 전체 길이=3, lo=0, hi=2입니다. i=(0+2)//2=1이고 j=(2+1+1)//2-1=1입니다. max_left1=nums1[0]=1, min_right1=nums1[1]=3, max_left2=nums2[0]=2, min_right2=inf(j=1=n)입니다. 확인 결과 1≤inf이고 2≤3입니다 ✓. 전체 길이가 홀수이므로 max(1,2)=2.0을 반환합니다. ✓ 배열 크기가 작기 때문에 알고리즘은 첫 단계에서 분할을 찾았습니다.
def find_median_traced(nums1, nums2):
if len(nums1) > len(nums2):
return find_median_traced(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
step = 0
while lo <= hi:
step += 1
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
ml1 = float('-inf') if i==0 else nums1[i-1]
mr1 = float('inf') if i==m else nums1[i]
ml2 = float('-inf') if j==0 else nums2[j-1]
mr2 = float('inf') if j==n else nums2[j]
print(f'Step {step}: i={i},j={j}, ml1={ml1},mr1={mr1},ml2={ml2},mr2={mr2}')
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
return 0.0
print(find_median_traced([1,3],[2]))더 짧은 배열에 이진 탐색을 하는 이유
O(log(m+n))이 아니라 O(log(min(m,n)))을 달성하기 위해 더 짧은 배열에 이진 탐색을 수행합니다. 긴 배열의 분할은 짧은 배열의 분할에 의해 완전히 결정됩니다. len(nums1) > len(nums2)이면 입력 배열을 교환하여 항상 짧은 배열을 탐색 공간으로 사용합니다. 불변 조건은 다음과 같습니다. j가 i와 전체 길이로부터 도출되면 j는 항상 nums2에 유효한 분할 인덱스입니다.
# Prove j is always valid:
# Total elements in left halves = (m+n+1)//2
# Left from nums1: i elements (0 <= i <= m)
# Left from nums2: j = (m+n+1)//2 - i elements
# j must be in [0, n]:
# j >= 0: i <= (m+n+1)//2 <= (m+n+1)//2 ≤ ... always true for valid lo/hi
# j <= n: i >= (m+n+1)//2 - n = (m-n+1)//2 >= 0 (since m <= n)
m, n = 3, 5 # m <= n
half = (m+n+1)//2
for i in range(m+1):
j = half - i
valid = 0 <= j <= n
print(f'i={i}: j={j}, valid={valid}')전체 길이가 짝수와 홀수인 경우 처리
합쳐진 길이가 홀수이면 중앙값은 왼쪽 절반의 최댓값입니다(max(max_left1, max_left2)). 짝수이면 왼쪽 절반의 최댓값과 오른쪽 절반의 최솟값을 평균 냅니다. 왼쪽 절반 크기에 대한 (m+n+1)//2 공식은 두 경우 모두 작동합니다. 전체 길이가 짝수이면 n//2가 되고(왼쪽에 원소가 하나 더 있음), 여기에 min_right를 사용해 평균을 내면 짝수 길이의 중앙값을 얻습니다.
def median_demo(a, b):
merged = sorted(a + b)
L = len(merged)
expected = merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2
computed = find_median_sorted_arrays(a[:], b[:])
print(f'a={a}, b={b}: merged={merged}, median={expected}, computed={computed}')
assert abs(expected - computed) < 1e-9
def find_median_sorted_arrays(nums1, nums2):
if len(nums1)>len(nums2): return find_median_sorted_arrays(nums2,nums1)
m,n=len(nums1),len(nums2); lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2; j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else nums1[i-1]; mr1=float('inf') if i==m else nums1[i]
ml2=float('-inf') if j==0 else nums2[j-1]; mr2=float('inf') if j==n else nums2[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
return 0.0
median_demo([1,3],[2])
median_demo([1,2],[3,4])
median_demo([],[1])
median_demo([2],[]) # single array경계 사례
중요한 경계 사례는 다음과 같습니다. (1) 한 배열이 비어 있음 — 비어 있지 않은 배열의 중앙값입니다. (2) 한 배열의 모든 원소가 다른 배열보다 작음 — 분할이 한쪽 끝에 놓입니다. (3) 중복 원소 — 알고리즘이 이를 자연스럽게 처리합니다. (4) 두 배열의 길이가 모두 1임 — 두 원소의 중앙값을 간단히 구합니다. 구현한 뒤에는 항상 이러한 사례를 테스트하십시오. -∞와 +∞라는 감시자 값이 경계 분할(i=0 또는 i=m)을 깔끔하게 처리합니다.
def fmsa(a,b):
if len(a)>len(b): return fmsa(b,a)
m,n=len(a),len(b); lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2; j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else a[i-1]; mr1=float('inf') if i==m else a[i]
ml2=float('-inf') if j==0 else b[j-1]; mr2=float('inf') if j==n else b[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
# Edge cases
print(fmsa([], [1])) # 1.0
print(fmsa([2], [])) # 2.0
print(fmsa([1,2], [3,4])) # 2.5
print(fmsa([3,4], [1,2])) # 2.5
print(fmsa([1,1,1], [1,1])) # 1.0 (duplicates)
print(fmsa([10,20,30],[5,15,25,35])) # 17.5일반화: 두 배열에서 k번째로 작은 원소
중앙값 문제는 정렬된 두 배열 전체에서 k번째로 작은 원소를 찾는 문제로 일반화할 수 있습니다. 각 단계에서 각 배열의 k//2번째 원소를 비교합니다. 더 작은 절반을 제거합니다. 해당 k//2개의 원소는 모두 k번째 원소보다 작으므로 버릴 수 있습니다. k를 k//2만큼 줄이고 재귀적으로 처리합니다. 기본 사례는 한 배열이 비어 있는 경우(남은 배열의 k번째 원소 반환) 또는 k=1인 경우(두 배열의 앞쪽 원소 중 최솟값 반환)입니다. 시간 복잡도는 O(log k) = O(log(m+n))입니다.
def kth_smallest(nums1, nums2, k):
if not nums1: return nums2[k-1]
if not nums2: return nums1[k-1]
if k == 1: return min(nums1[0], nums2[0])
# Compare k//2-th elements
half = k // 2
i = min(half, len(nums1)) - 1 # index in nums1
j = min(half, len(nums2)) - 1 # index in nums2
if nums1[i] <= nums2[j]:
# Eliminate first (i+1) elements of nums1
return kth_smallest(nums1[i+1:], nums2, k - (i+1))
else:
return kth_smallest(nums1, nums2[j+1:], k - (j+1))
nums1, nums2 = [1,3,5,7], [2,4,6,8]
for k in range(1, 9):
print(f'k={k}: {kth_smallest(nums1[:], nums2[:], k)}')모든 접근법 비교
최종 비교: 배열 병합: O(m+n) time, O(m+n) 공간. 분할 지점 이진 탐색: O(log(min(m,n))) time, O(1) 공간. k번째 최솟값 재귀: O(log(m+n)) time, O(log k) 호출 스택. 이 문제에서 면접관이 기대하는 방법은 분할 지점 이진 탐색 방법입니다. 명확하게 설명하기 가장 어려운 일반적인 LeetCode 문제이므로, 분할 논리와 네 가지 경계 조건 확인을 자동으로 수행할 수 있을 때까지 연습하십시오.
# Performance comparison
import time, random
def merge_median(a, b):
merged = sorted(a+b)
L=len(merged)
return merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2
def binary_median(a, b):
if len(a)>len(b): return binary_median(b,a)
m,n=len(a),len(b);lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2;j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else a[i-1];mr1=float('inf') if i==m else a[i]
ml2=float('-inf') if j==0 else b[j-1];mr2=float('inf') if j==n else b[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
for size in [100, 10000]:
a = sorted(random.sample(range(size*2), size))
b = sorted(random.sample(range(size*2), size))
t1=time.time(); [merge_median(a,b) for _ in range(1000)]; t1=time.time()-t1
t2=time.time(); [binary_median(a,b) for _ in range(1000)]; t2=time.time()-t2
print(f'n={size}: merge={t1:.4f}s, binary={t2:.4f}s, speedup={t1/t2:.1f}x')면접 의사소통 전략
면접에서 이 어려운 문제를 풀 때는 다음과 같이 하십시오. (1) 단순한 O(m+n) 병합 접근법을 즉시 제시하십시오. 이는 역량을 보여 줍니다. (2) O(log(min(m,n)))이라는 목표와 분할 아이디어를 설명하십시오. (3) 분할 불변식을 따라가며 설명하십시오. 왼쪽 최댓값1 ≤ 오른쪽 최솟값2 및 왼쪽 최댓값2 ≤ 오른쪽 최솟값1이어야 합니다. (4) 센티널 값을 명시적으로 처리하십시오. (5) 홀수와 짝수에 대한 중앙값 공식을 말하십시오. (6) 1~2개의 예로 확인하십시오. 이 5단계 프레임워크는 압박 속에서 완벽하게 해결하는 지원자가 드문 문제에서도 체계적인 문제 해결 능력을 보여 줍니다.
# Clean final solution for interviews:
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
return findMedianSortedArrays(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
max_l1 = nums1[i-1] if i > 0 else float('-inf')
min_r1 = nums1[i] if i < m else float('inf')
max_l2 = nums2[j-1] if j > 0 else float('-inf')
min_r2 = nums2[j] if j < n else float('inf')
if max_l1 <= min_r2 and max_l2 <= min_r1:
if (m + n) % 2:
return float(max(max_l1, max_l2))
return (max(max_l1, max_l2) + min(min_r1, min_r2)) / 2.0
elif max_l1 > min_r2: hi = i - 1
else: lo = i + 1
# Time: O(log(min(m,n))), Space: O(1)
print(findMedianSortedArrays([1,3],[2])) # 2.0
print(findMedianSortedArrays([1,2],[3,4])) # 2.5빠른 확인
이 수업에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 이해했는지 확인해 보십시오.
수업 요약
이 수업에서는 다음을 배웠습니다. 두 정렬 배열의 중앙값은 더 짧은 배열에서 올바른 분할 경계를 이진 탐색하여 O(log(min(m,n)))에 구할 수 있습니다. 분할은 왼쪽 최댓값1 ≤ 오른쪽 최솟값2 및 왼쪽 최댓값2 ≤ 오른쪽 최솟값1일 때 유효하며, 센티널 값으로 경계 상황을 처리합니다. 또한 k번째 최솟값 일반화는 O(log k) time의 재귀적 절반 제거 접근법을 사용합니다. 분할 정복 수업을 모두 마치신 것을 축하합니다. 이제 코딩 면접을 위한 종합적인 도구 모음을 갖추셨습니다!
자주 묻는 질문
“정렬된 두 배열의 중앙값” 강의는 무료인가요?
네 — “정렬된 두 배열의 중앙값” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“정렬된 두 배열의 중앙값”에서 뭘 배우나요?
더 짧은 배열의 분할 경계에 이진 탐색을 적용해 O(log(min(m,n))) 시간에 두 정렬 배열의 중앙값을 구합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“정렬된 두 배열의 중앙값” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 분할 정복 템플릿
- 수정된 병합 정렬로 역전쌍 세기
- 과반수 원소: Boyer-Moore 투표
- 정렬된 두 배열의 중앙값