2つのソート済み配列の中央値
短い方の配列の分割位置を二分探索し、O(log(min(m,n)))でmedian-of-two-sorted-arraysを解きます。
「2つのソート済み配列の中央値」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
2つのソート済み配列の中央値
2つのソート済み配列の中央値 (LeetCode 4) は、典型的な難問です。長さ m の nums1 と長さ n の nums2 という2つのソート済み配列が与えられたとき、結合後のソート済み列の中央値を O(log(min(m,n))) 時間で求めます。素朴な方法では両方の配列を 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) のアプローチは、両方のソート済み配列をマージしてから中央値を求める方法です。2つのソート済み配列のマージには 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パーティションの考え方
重要な洞察は、中央値によって結合配列が同じ大きさの2つの半分に分割されるということです。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、total=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（左側に要素が1つ多い状態）となり、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の場合 — 2要素の中央値を求めるだけです。実装後は必ずこれらのケースをテストしてください。センチネル値 -∞ と +∞ により、境界上のパーティション（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一般化: 2つの配列における k 番目に小さい要素
中央値の問題は、2つのソート済み配列全体から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) の時間計算量、O(m+n) の空間計算量。分割点に対する二分探索: O(log(min(m,n))) の時間計算量、O(1) の空間計算量。k 番目に小さい要素の再帰: O(log(m+n)) の時間計算量、O(log k) のコールスタックです。分割点に対する二分探索法が、この問題で面接官が期待する方法です。これは、明確に説明するのが最も難しい、よく出題される LeetCode 問題です。分割のロジックと4つの境界チェックを、自然にできるようになるまで練習してください。
# 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) 分割の不変条件である max_left1 ≤ min_right2 と max_left2 ≤ min_right1 を順に説明します。(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理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認してください。
レッスンのまとめ
このレッスンでは、2つのソート済み配列の中央値は、短い方の配列で正しい分割境界を二分探索することで、O(log(min(m,n))) で求められること、分割が有効になるのは max_left1 ≤ min_right2 かつ max_left2 ≤ min_right1 のときであり、センチネル値によって境界の場合にも対応できること、そしてk 番目に小さい要素への一般化では、O(log k) 時間の再帰的な半分削減アプローチを使うことを学びました。分割統治のレッスンを修了おめでとうございます。これで、コーディング面接に向けた包括的なツールキットが身につきました。
よくある質問
「2つのソート済み配列の中央値」レッスンは無料ですか？
はい。「2つのソート済み配列の中央値」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「2つのソート済み配列の中央値」で何を学びますか？
短い方の配列の分割位置を二分探索し、O(log(min(m,n)))でmedian-of-two-sorted-arraysを解きます。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「2つのソート済み配列の中央値」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 分割統治のテンプレート
- 変更版マージソートで転倒数を数える
- 多数派要素：Boyer-Moore投票法
- 2つのソート済み配列の中央値