2D Matrix Binary Search

効率的な二分探索アルゴリズムの技術解説

アルゴリズム概要

問題設定

ソート済み2次元行列において、指定されたターゲット値を効率的に検索する。 各行は昇順ソート、かつ各行の先頭要素は前行の末尾要素より大きい。

アプローチ

2次元行列を1次元配列として扱い、座標変換を使用して二分探索を実行。 O(log(m×n))の時間計算量を実現。

最適化

Python固有の特性を活用し、整数演算の効率性と型ヒントによる可読性を両立。 メモリ使用量O(1)で実装。

ステップバイステップ解説

1
入力検証とサイズ取得

まず、入力行列が空でないことを確認し、行数（n）と列数（m）を取得します。

Step 1: Input Validation 
if not matrix or not matrix[0]:
    return False

n, m = len(matrix), len(matrix[0])  # n=行数, m=列数
2
二分探索の初期化

1次元配列として扱うため、leftを0、rightを(n×m-1)に設定します。

Step 2: Binary Search Initialization 
left, right = 0, n * m - 1  # 1次元配列のインデックス範囲
3
座標変換と値の取得

1次元インデックスmidを2次元座標に変換し、該当する値を取得します。

Step 3: Coordinate Conversion 
mid = (left + right) // 2
# 座標変換: 1D index → 2D coordinates
row = mid // m  # 行インデックス
col = mid % m   # 列インデックス
val = matrix[row][col]  # 実際の値を取得
4
値の比較と範囲更新

取得した値とターゲットを比較し、探索範囲を半分に絞り込みます。

Step 4: Value Comparison 
if val == target:
    return True  # 見つかった！
elif val < target:
    left = mid + 1  # 右半分を探索
else:
    right = mid - 1  # 左半分を探索

完全なコード実装

Python Implementation 
from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        """
        2D行列内を二分探索で探索する
        行列は「各行がソート済み」「行の先頭が前行の末尾より大きい」という条件を満たす

        時間計算量: O(log(m * n))
        空間計算量: O(1)
        """
        # Step 1: 入力検証
        if not matrix or not matrix[0]:
            return False

        # Step 2: 行列のサイズを取得
        n, m = len(matrix), len(matrix[0])

        # Step 3: 二分探索の初期化
        left, right = 0, n * m - 1

        # Step 4: 二分探索のメインループ
        while left <= right:
            # 中央のインデックスを計算
            mid = (left + right) // 2

            # 1D → 2D 座標変換
            row = mid // m
            col = mid % m
            val = matrix[row][col]

            # 値を比較して探索範囲を更新
            if val == target:
                return True
            elif val < target:
                left = mid + 1
            else:
                right = mid - 1

        # Step 5: 見つからなかった場合
        return False

# 使用例とテストケース
def test_search_matrix():
    solution = Solution()

    # Test Case 1
    matrix1 = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
    assert solution.searchMatrix(matrix1, 3) == True
    assert solution.searchMatrix(matrix1, 13) == False

    # Test Case 2
    matrix2 = [[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]]
    assert solution.searchMatrix(matrix2, 5) == True
    assert solution.searchMatrix(matrix2, 20) == False

    print("All test cases passed! ✅")

if __name__ == "__main__":
    test_search_matrix()

インタラクティブデモ

2D行列の視覚化

デモを開始してください

計算量解析

時間計算量

O(log(m×n))

二分探索により、各ステップで探索範囲を半分に削減

空間計算量

O(1)

固定数の変数のみ使用、入力サイズに依存しない

最大ステップ数

⌈log₂(m×n)⌉

例: 3×4行列では最大4ステップで完了

計算量の比較

Linear Search

O(m×n)

最悪: 全要素チェック

Binary Search

O(log(m×n))

効率的: 毎回半分に削減

パフォーマンス分析

Python固有の最適化ポイント

✅ 効率的な演算

  • 整数除算 // とモジュロ % の活用
  • CPythonのC実装による高速化
  • ビットシフトより可読性重視

📝 可読性の向上

  • 型ヒントによる静的解析対応
  • 明確な変数名の使用
  • ドキュメント文字列の充実
最適化比較例 
# ❌ 非効率な実装例
def searchMatrix_slow(matrix, target):
    for row in matrix:
        for val in row:
            if val == target:
                return True
    return False  # O(m×n) - 全要素をチェック

# ✅ 最適化された実装
def searchMatrix_optimized(matrix, target):
    if not matrix or not matrix[0]:
        return False

    n, m = len(matrix), len(matrix[0])
    left, right = 0, n * m - 1

    while left <= right:
        mid = (left + right) // 2  # C実装で高速
        val = matrix[mid // m][mid % m]  # 効率的な座標変換

        if val == target:
            return True
        elif val < target:
            left = mid + 1
        else:
            right = mid - 1

    return False  # O(log(m×n)) - 指数的に高速