二分探索で 2 つのソート済み配列の中央値を求める｜コーディング面接問題

問題

小さい順に並んだ整数の並び nums1 と nums2 を受け取ります。2 つを合わせて小さい順に並べたときの中央値を返す関数を書いてください。

中央値は、合わせた個数が奇数なら真ん中の値、偶数なら真ん中の 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 つで、真ん中は 4 です。

入力

nums1 = [1, 4, 9]
nums2 = [2, 6]

出力

例 2

合わせると [3, 5, 8, 10] の 4 つで、真ん中の 2 つは 5 と 8 です。平均は 6.5 です。

入力

nums1 = [3, 8]
nums2 = [5, 10]

出力

6.5

例 3

片方が空です。

入力

nums1 = []
nums2 = [7]

出力

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

「ソート済みの配列が 2 つあります。まとめたときの中央値を求めてください」
最初にまとめる書き方を出すと、「O(m + n) は分かりました。対数時間にできますか？」と一段下げるよう求められます
書き終えたあとに「片方が空なら？」「なぜ短い方で探すのですか？」と、端の場合と理由を確かめられます

この問題は、二分探索で「値」ではなく「切る位置」を探す形です。何を探すのかを先に言葉にすると、条件を落としにくくなります。

アルゴリズムのチートシートの「ソートと二分探索」に、この型の要点を表とコードでまとめています。

まず考える手順

段 1

まずは素直な書き方です。マージソートのまとめる手順で、2 つの並びの先頭から小さい方を取っていき、真ん中まで進めば中央値が分かります。時間は O(m + n) です。

段 2

見方を変えます。合わせた並びを「左の半分」と「右の半分」に分けたとき、左の半分は nums1 の先頭 i 個と nums2 の先頭 j 個でできています。左の半分の個数を half = (m + n + 1) // 2 と決めておけば、i を決めると j は half - i で決まります。つまり、探すのは i ただ 1 つです。

段 3

i が正しい切り方かは、切れ目の両側 4 つの値で分かります。nums1 の左端の最後を al、右の最初を ar、nums2 も同じく bl と br とすると、al <= br かつ bl <= ar なら正しい切り方です。al > br なら nums1 から取りすぎなので i を減らし、bl > ar なら取り足りないので i を増やします。この向きがはっきりしているので、i を二分探索で探せます。

段 4

切れ目が並びの端に来たときは、無い側の値を「とても小さい数」や「とても大きい数」と見ます。こうすると比べの式を分けずに済みます。正しい切り方が見つかったら、奇数なら max(al, bl)、偶数ならそれと min(ar, br) の平均が答えです。i は短い方の並びで探すと、j が負にも長さ超えにもならず、回数も短い方で決まります。

解答

Python

def find_median(nums1, nums2):
    a, b = nums1, nums2
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    half = (m + n + 1) // 2
    inf = float("inf")

    def at(x, k):
        if k < 0:
            return -inf
        if k >= len(x):
            return inf
        return x[k]

    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - i
        al = at(a, i - 1)
        ar = at(a, i)
        bl = at(b, j - 1)
        br = at(b, j)
        if al > br:
            hi = i - 1
        elif bl > ar:
            lo = i + 1
        else:
            left = max(al, bl)
            if (m + n) % 2 == 1:
                return left
            right = min(ar, br)
            total = left + right
            return total / 2

JavaScript

function findMedian(
  nums1, nums2
) {
  let a = nums1;
  let b = nums2;
  if (a.length > b.length) {
    [a, b] = [b, a];
  }
  const m = a.length;
  const n = b.length;
  const half = (m + n + 1) >> 1;
  const { max, min } = Math;
  const at = (x, k) => {
    if (k < 0) {
      return -Infinity;
    }
    if (k >= x.length) {
      return Infinity;
    }
    return x[k];
  };
  let lo = 0;
  let hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1;
    const j = half - i;
    const al = at(a, i - 1);
    const ar = at(a, i);
    const bl = at(b, j - 1);
    const br = at(b, j);
    if (al > br) {
      hi = i - 1;
    } else if (bl > ar) {
      lo = i + 1;
    } else {
      const left = max(al, bl);
      if ((m + n) % 2 === 1) {
        return left;
      }
      const right = min(ar, br);
      return (left + right) / 2;
    }
  }
  return 0;
}

Go

import "math"

func findMedian(
	nums1, nums2 []int,
) float64 {
	a, b := nums1, nums2
	if len(a) > len(b) {
		a, b = b, a
	}
	m, n := len(a), len(b)
	half := (m + n + 1) / 2
	at := func(x []int, k int,
	) int {
		if k < 0 {
			return math.MinInt
		}
		if k >= len(x) {
			return math.MaxInt
		}
		return x[k]
	}
	lo, hi := 0, m
	for lo <= hi {
		i := (lo + hi) / 2
		j := half - i
		al := at(a, i-1)
		ar := at(a, i)
		bl := at(b, j-1)
		br := at(b, j)
		if al > br {
			hi = i - 1
		} else if bl > ar {
			lo = i + 1
		} else {
			left := max(al, bl)
			if (m+n)%2 == 1 {
				return float64(left)
			}
			right := min(ar, br)
			s := float64(left + right)
			return s / 2
		}
	}
	return 0
}

正しい切り方は必ず 1 つあるので、繰り返しの中で必ず返ります。JavaScript と Go の最後の return 0 は、言語が「どの道でも値を返す」ことを求めるために置いているだけで、通りません。

計算量

時間は O(log(min(m, n))) です。短い方の並びの切る位置 0 から m までを、毎回半分に狭めます
使う記憶は O(1) です。並びを写さず、位置と値の置き場だけを使います

よくある間違い

長い方で i を探す。長い方を切ると j = half - i が負になったり、短い方の長さを超えたりして、範囲の外を読みます。最初に短い方を a にそろえます
half を (m + n) // 2 にする。 合わせた個数が奇数のとき、真ん中の値が右の半分に入り、max(al, bl) では取れません。(m + n + 1) // 2 にして、奇数のときは左の半分を 1 つ多くします
端の値の置き換えを忘れる。 i が 0 や m のとき、a[i - 1] や a[i] は無い所です。Python の a[-1] は止まらずに末尾を返すので、間違いに気づきにくくなります
整数どうしの割り算で小数を落とす。 Go で (left + right) / 2 と整数のまま割ると、6.5 が 6 になります。先に float64 に直してから割ります

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

二分探索で 2 つのソート済み配列の中央値を求める

問題