Pythonでソート済み2D行列を効率的に検索する方法（Search a 2D Matrix II）

問題の概要

m × n の行列が与えられたとき、その中から特定の値を効率的に検索するアルゴリズムを実装することを考えます。この行列には、以下のような性質があります。

• 各行の整数は、左から右に向かって昇順に並んでいる
• 各列の整数は、上から下に向かって昇順に並んでいる

行列の例

たとえば、次のような5×5の行列を考えてみましょう。

このとき、検索対象（target）が「5」であれば True を返し、「20」であれば False を返します。

アルゴリズムの考え方

この問題を効率的に解く鍵となるのは、行列の右上隅から探索を始めることです。右上の要素に注目すると、次のような性質が成り立ちます。

• 現在の値がターゲットより大きい場合 → ターゲットは同じ行の左側にしか存在しないため、列番号を1つ減らす
• 現在の値がターゲットより小さい場合 → ターゲットは同じ列の下側にしか存在しないため、行番号を1つ増やす
• 現在の値がターゲットと一致した場合 → True を返して終了する

この操作を繰り返すことで、二分探索を使わずとも、最悪でも O(m + n) の時間計算量で検索が完了します。

具体的な手順

• 列数を len とし、開始位置を行インデックス c1 := 0、列インデックス c2 := len − 1 に設定する
• 以下の処理を繰り返す：
  • matrix[c1][c2] == target ならば True を返す
  • matrix[c1][c2] > target ならば c2 を 1 減らして続行する
  • それ以外の場合は c1 を 1 増やす
  • c1 が行数以上になったか、c2 が 0 未満になった場合は False を返す

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def searchMatrix(self, matrix, target):
        try:
            length = len(matrix[0])
            counter1, counter2 = 0, length-1
            while True:
                if matrix[counter1][counter2] == target:
                    return True
                elif matrix[counter1][counter2] > target:
                    counter2 -= 1
                    continue
                counter1 = counter1 + 1
                if counter1 >= len(matrix) or counter2 < 0:
                    return False
        except:
            return False

ob1 = Solution()
print(ob1.searchMatrix([[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], 5))

入力

[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
5

出力

True

まとめ

右上隅から階段状に探索範囲を絞り込んでいくこの手法（スターケイスサーチ）により、ソート済みの2D行列に含まれる値を O(m + n) の計算量で高速に検索できます。また、実装では try-except を用いて空の行列などの異常な入力にも対応しており、堅牢性の高いコードになっています。行・列それぞれが独立にソートされている行列の検索では、このアプローチが非常に有効ですので、ぜひ覚えておきましょう。