二分探索で 2 つの ソート済み配列の 中央値を求める - LeetCode 4
小さい
海外で定番の問題リスト 4 本のうち 2 本に入っています (NeetCode 150、LeetCode Top Interview 150)
問題
小さいnums1 と nums2 を
- 中央値は、
合わせた 個数が 奇数なら 真ん中の 値、 偶数なら 真ん中の 2 つの平均です - 戻り値は
数です。 平均が 小数に なる ときは 6.5のように返します。 ちょうど 整数に なる ときは、 6と返しても 6.0と返しても 同じと 見ます (例の 出力は 6と書きます) nums1とnums2の長さは それぞれ 0 以上 1000 以下で、 合わせて 1 つ以上 あります。 値は どれも -1000000 以上 1000000 以下です - 長さを m と n として、
2 つを まとめる O(m + n) ではなく、 O(log(min(m, n))) で 求めてください
入力と出力の例
例 1
合わせると [1, 2, 4, 6, 9] の 5 つで、
入力
nums1 = [1, 4, 9]
nums2 = [2, 6]出力
4例 2
合わせると [3, 5, 8, 10] の 4 つで、
入力
nums1 = [3, 8]
nums2 = [5, 10]出力
6.5例 3
片方が空です。
入力
nums1 = []
nums2 = [7]出力
7図で見る
例 1 で、
面接での聞かれ方
面接では、
- 「ソート済みの
配列が 2 つあります。 まとめた ときの 中央値を 求めてください」 - 最初に
まとめる 書き方を 出すと、 「O(m + n) は 分かりました。 対数時間に できますか?」と 一段下げるよう 求められます - 書き終えた
あとに 「片方が空なら?」 「なぜ短い方で 探すのですか?」と、 端の 場合と 理由を 確かめられます
この
ヒント
まだ開いていません
付箋は 4 枚。下の段ほど答えに近づきます
ヒント 2
ヒント 3
ヒント 4答えに近い
アルゴリズムのチートシートの「ソートと二分探索」に、
関わる学び
二分探索は、
まず 考える手順
段 1
まずは
段 2
見方をnums1 のcut1 個と nums2 のcut2 個でhalf = (count + 1) // 2 とcut1 をcut2 は half - cut1 でcount は 2 つをcut1 ただ 1 つです。
段 3
cut1 がnums1 のleft1、right1、nums2 もleft2 と right2 とleft1 <= right2 かつ left2 <= right1 ならleft1 > right2 なら nums1 からcut1 をleft2 > right1 ならcut1 をcut1 を
段 4
切れ目がmax(left1, left2)、min(right1, right2) のcut1 はcut2 がnums1 のnums1 と nums2 をnums1 を
解答
Python
Python
INF = float("inf")
def find_median(
nums1: list[int],
nums2: list[int],
) -> float:
# nums1 を短い方にそろえる
if len(nums1) > len(nums2):
return find_median(nums2, nums1)
count = len(nums1)
count += len(nums2)
half = (count + 1) // 2
low = 0
high = len(nums1)
while low <= high:
cut1 = (low + high) // 2
cut2 = half - cut1
left1, right1 = edges(
nums1, cut1,
)
left2, right2 = edges(
nums2, cut2,
)
if left1 > right2:
high = cut1 - 1
elif left2 > right1:
low = cut1 + 1
else:
return middle(
count,
left1, left2,
right1, right2,
)
def edges(
nums: list[int],
cut: int,
) -> tuple[float, float]:
# 切れ目の左の最後と右の最初
left = -INF
if cut > 0:
left = nums[cut - 1]
right = INF
if cut < len(nums):
right = nums[cut]
return left, right
def middle(
count: int,
left1: float,
left2: float,
right1: float,
right2: float,
) -> float:
left = max(left1, left2)
if count % 2 == 1:
return left
right = min(right1, right2)
both = left + right
return both / 2JavaScript
JavaScript
function findMedian(nums1, nums2) {
if (nums1.length > nums2.length) {
return findMedian(nums2, nums1);
}
let count = nums1.length;
count += nums2.length;
const half = (count + 1) >> 1;
let low = 0;
let high = nums1.length;
while (low <= high) {
const cut1 = (low + high) >> 1;
const cut2 = half - cut1;
const [left1, right1] =
edges(nums1, cut1);
const [left2, right2] =
edges(nums2, cut2);
if (left1 > right2) {
high = cut1 - 1;
} else if (left2 > right1) {
low = cut1 + 1;
} else {
return middle(
count,
left1, left2,
right1, right2);
}
}
return 0;
}
// 切れ目の左の最後と右の最初
function edges(nums, cut) {
let left = -Infinity;
if (cut > 0) {
left = nums[cut - 1];
}
let right = Infinity;
if (cut < nums.length) {
right = nums[cut];
}
return [left, right];
}
function middle(
count, left1, left2,
right1, right2
) {
const left = Math.max(left1, left2);
if (count % 2 === 1) {
return left;
}
const right = Math.min(
right1, right2);
const both = left + right;
return both / 2;
}Go
Go
import "math"
func findMedian(
nums1, nums2 []int,
) float64 {
if len(nums1) > len(nums2) {
return findMedian(nums2, nums1)
}
count := len(nums1)
count += len(nums2)
half := (count + 1) / 2
low, high := 0, len(nums1)
for low <= high {
cut1 := (low + high) / 2
cut2 := half - cut1
left1, right1 := edges(nums1, cut1)
left2, right2 := edges(nums2, cut2)
if left1 > right2 {
high = cut1 - 1
} else if left2 > right1 {
low = cut1 + 1
} else {
return middle(
count,
left1, left2,
right1, right2)
}
}
return 0
}
// 切れ目の左の最後と右の最初
func edges(
nums []int, cut int,
) (int, int) {
left := math.MinInt
if cut > 0 {
left = nums[cut-1]
}
right := math.MaxInt
if cut < len(nums) {
right = nums[cut]
}
return left, right
}
func middle(
count, left1, left2 int,
right1, right2 int,
) float64 {
left := max(left1, left2)
if count%2 == 1 {
return float64(left)
}
right := min(right1, right2)
both := left + right
return float64(both) / 2
}正しいreturn 0 は、
計算量
- 時間は O(log(min(m, n))) です。
短い方の 並びの 切る 位置 0 から m までを、 毎回 半分に狭めます - 使う
記憶は O(1) です。 並びを 写さず、 位置と 値の 置き場だけを使います
よく ある間違い
- 長い方で
cut1を探す。 長い方を切ると cut2 = half - cut1が負に なったり、 短い方の 長さを 超えたりして、 範囲の 外を 読みます。 最初に 短い方を nums1にそろえます halfをcount // 2にする。 合わせた個数が 奇数の とき、 真ん中の 値が 右の 半分に 入り、 max(left1, left2)では取れません。 (count + 1) // 2にして、 奇数の ときは 左の 半分を 1 つ 多くします - 端の
値の 置き換えを忘れる。 cut1が 0 やnums1の長さの とき、 nums1[cut1 - 1]やnums1[cut1]は無い所です。 Python の nums1[-1]は止まらずに 末尾を 返すので、 間違いに 気づきにくくなります - 整数どうしの
割り算で 小数を落とす。 Go で both / 2と整数のまま 割ると、 6.5 が 6 に なります。 先に float64に直してから割ります
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での 話し方の例
書き始める
「まと
めれば O(m + n) ですが、 中央値は 合わせた 並びを 左右半分に 分ける 切れ目だけで 決まります。 左の 半分の 個数は 決まっているので、 短い方の 並びを 何個取るかの cut1を決めれば、 もう 片方は 自動で 決まります。 切れ目の 両側の 値の 大小で cut1を増やすか 減らすかが 分かるので、 cut1を二分 探索します。 時間は O(log(min(m, n)))、 記憶は O(1) です。」
書き終えたら、
「例 1 では
短い方は [2, 6]で、左の 半分は 3 個です。 cut1を 1 にすると、 短い方から 2、 長い方から 1 と 4 を 取ります。 2 は 9 以下、 4 は 6 以下なので 正しい 切り方です。 合わせて 5 個で 奇数なので、 左の 最大の 4 が 答えです。」