Pythonで行と列がソートされた2次元行列からターゲット値を検索するプログラム

各行および各列が非降順（昇順）にソートされた2次元行列があるとします。このとき、指定されたターゲット値がその行列の中に存在するかどうかを判定する問題です。

問題の例

例えば、以下のような行列が与えられたとします。

ここでターゲット値が 31 の場合、行列内に存在するため、出力は True となります。

解法のアプローチ

この問題は、行列の右上隅から探索を開始する「階段探索（スティンケースサーチ）」と呼ばれる手法で効率的に解くことができます。手順は以下の通りです。

• 探索開始位置の列インデックス col を「列数 − 1」（つまり右端の列）に設定します。
• 行インデックス i を 0 から行数まで順に処理します。
  • 現在の要素 matrix[i][col] がターゲットより大きい間、col を1ずつ減らして左へ移動します。
  • matrix[i][col] がターゲットと一致すれば、True を返します。
• すべての行を調べて見つからなければ、False を返します。

この方法では、各ステップで探索範囲が1行または1列ずつ確実に狭まるため、計算量は O(行数 + 列数) となり、全要素をなぞる O(行数 × 列数) よりも高速です。

実装例

class Solution:
    def solve(self, matrix, target):
        col = len(matrix[0]) - 1
        for i in range(len(matrix)):
            while matrix[i][col] > target and col >= 0:
                col = col - 1
            if matrix[i][col] == target:
                return True
        return False

ob = Solution()
matrix = [
    [2, 4, 30],
    [3, 4, 31],
    [6, 6, 32]
]
target = 31
print(ob.solve(matrix, target))

入力

matrix = [
[2, 4, 30],
[3, 4, 31],
[6, 6, 32]]
target = 31

出力

True

補足：実用上の注意点

実際のコードでは、col が負の値になった場合の参照エラー（IndexError）を避けるため、while ループの条件やリスト参照時に境界チェックを追加すると安全です。また、行列が空の場合や行の長さが0の場合への対処も加えておくと、より堅牢な実装になります。