二分探索で行ごとに並んだ表から値を探す

二分探索問題 84

各行が小さい順に並び、行の頭が前の行の最後より大きい表から、目標の値があるかを返します。表を 1 本の長い並びと見なして二分探索する練習です。

海外で定番の問題リスト 4 本には入っていません

問題

整数の表 matrix と目標の値 target を受け取ります。target が表のどこかにあれば true、無ければ false を返す関数を書いてください。

表は m 行 n 列で、どの行も左から小さい順に並んでいます
どの行も、頭の値が 1 つ前の行の最後の値より大きくなっています。つまり、上の行から左から右へ読むと、全体が小さい順の 1 本の並びになります
同じ値は 2 回出てきません
m と n はどちらも 1 以上 100 以下、値と target はどれも -10000 以上 10000 以下です
時間は O(log(m × n)) で解いてください

入力と出力の例

例 1

社員番号の表です。上の行から左から右へ読むと 2、5、9、14、17、21、26、30、33、38、41、47 と並び、21 は 2 行目の 2 列目にあります。

matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 41, 47]] target = 21

true

例 2

15 は 1 行目の最後の 14 と 2 行目の頭の 17 のあいだに入るはずの値で、表にはありません。

matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 41, 47]] target = 15

false

例 3

1 列だけの表です。いちばん下の値も見つけられます。

matrix = [[-8], [-3], [4], [10]] target = 10

true

面接での聞かれ方

二分探索の応用として、ミドルの面接でよく出ます。

「行ごとに並んだ表から値を探してください。全部を見るより速くできますか？」
書き終えたあとに「行の頭が前の行の最後より大きい、という決まりが無かったらどうしますか？」と続きを聞かれることがあります。そのときは右上の角から始め、大きければ左へ、小さければ下へ進む O(m + n) の書き方になります
「行で 1 回、列で 1 回の 2 段の二分探索でも書けますか？」と聞かれることもあります

ミドルの問題なので、表の位置と 1 本の並びの番号を行き来する式を、迷わず書けるかが見られます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

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

二分探索は、並んだデータの範囲を半分ずつ絞ります。100 万件でも 20 回ほどで 1 件になります。

まず考える手順

段 1

まずは素直に、全部のマスを順に見る書き方を考えます。O(m × n) で動きますが、行が並んでいるという手がかりを使っていません。

段 2

上の行から左から右へ読むと、全体が小さい順の 1 本の並びです。この並びの k 番目は、表の k // n 行目、k % n 列目にあります。n は 1 行の長さです。

段 3

番号 0 から m × n − 1 の範囲で、ふつうの二分探索をします。まん中の番号 mid を表の位置に直して値を読み、target と同じなら見つかった、小さければ右半分、大きければ左半分に絞ります。

段 4

範囲が空になったら、target は表にありません。表を 1 本の並びに作り直さず、番号から位置を計算するだけなので、余分な記憶も使いません。

解答

Python

def sorted_matrix_search(
    matrix, target
):
    m = len(matrix)
    n = len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        row = matrix[mid // n]
        v = row[mid % n]
        if v == target:
            return True
        if v < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

JavaScript

function sortedMatrixSearch(
  matrix, target
) {
  const m = matrix.length;
  const n = matrix[0].length;
  let lo = 0;
  let hi = m * n - 1;
  while (lo <= hi) {
    const mid =
      Math.floor((lo + hi) / 2);
    const v = matrix[
      Math.floor(mid / n)
    ][mid % n];
    if (v === target) {
      return true;
    }
    if (v < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return false;
}

Go

func sortedMatrixSearch(
	matrix [][]int, target int,
) bool {
	m := len(matrix)
	n := len(matrix[0])
	lo, hi := 0, m*n-1
	for lo <= hi {
		mid := (lo + hi) / 2
		v := matrix[mid/n][mid%n]
		if v == target {
			return true
		}
		if v < target {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	return false
}

mid // n が行、mid % n が列です。割るのは列の数 n で、行の数 m ではありません。

計算量

時間は O(log(m × n)) です。1 回比べるごとに、残りの範囲が半分になります
使う記憶は O(1) です。範囲の両端とまん中の番号だけを持ちます

よくある間違い

行の数 m で割る。番号から位置に直すときは、1 行の長さ n で割ります。m で割ると、行と列の数が違う表で別のマスを読みます
範囲の右端を m × n にする。 lo <= hi で回す書き方なら、右端は最後の番号の m × n − 1 です。m × n にすると表の外を読みます
行を探す段で、行の頭だけを見て終える。 2 段の二分探索で書くとき、target は「頭が target 以下の最後の行」にあります。頭がちょうど同じ行だけを探すと、例 1 の 21 を見落とします
全部を 1 本の並びに作り直す。並びを作るだけで O(m × n) の時間と記憶を使い、二分探索にした意味がなくなります

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def sorted_matrix_search(matrix: list[list[int]], target: int) -> bool:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(sorted_matrix_search([[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 41, 47]], 21))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します