C#で行ごとに増加する行列を効率的に検索する方法

この問題に対する最も単純な解決策は、入力された行列に格納されているすべての要素を順番に走査し、指定されたキーを探すことです。しかし、この線形探索のアプローチでは、行列のサイズが M×N の場合、計算量は O(MN) となり、大規模な行列では非効率です。

そこで有効なのが、行列を右上から走査する手法です。探索対象の要素が現在注目している右上の要素より大きければ行を1つ進め（インクリメント）、小さければ列を1つ戻す（デクリメント）ことで、効率的に検索を行えます。この方法により、計算量を O(M+N) まで削減できます。

以下のコードでは、2次元配列と検索キーを引数として受け取り、検索の成否に応じて true または false を返すメソッド SearchRowwiseIncrementedMatrix を実装しています。

コード例

public class Matrix{
    public bool SearchRowwiseIncrementedMatrix(int[] mat, int searchElement){
        int row = getMatrixRowSize(mat);
        int col = getMatrixColSize(mat) - 1;
        int r = 0;

        while (col >= 0 && r < row){
            if (mat[r, col] == searchElement){
                return true;
            }
            else if (searchElement < mat[r, col]){
                col--;
            }
            else{
                r++;
            }
        }
        return false;
    }

    private int getMatrixRowSize(int[] mat){
        return mat.GetLength(0);
    }
    private int getMatrixColSize(int[] mat){
        return mat.GetLength(1);
    }
}

static void Main(string[] args){
    Matrix m = new Matrix();
    int[] mat = new int[3, 4] { { 1, 7, 10, 19 }, { 2, 8, 11, 20 }, { 3, 9, 12, 21 } };
    Console.WriteLine(m.SearchRowwiseIncrementedMatrix(mat, 11));
}

実行結果

TRUE

アルゴリズムのポイント

• 開始位置： 行列の右上隅（最初の行の最後の列）から探索を開始します。
• 一致した場合： 探索キーと現在の要素が等しければ true を返します。
• 探索キーが小さい場合： 現在の列より左側にしか存在しないため、列をデクリメントします。
• 探索キーが大きい場合： 現在の行より下側にしか存在しないため、行をインクリメントします。

このように、各行・各列が昇順にソートされた行列の特性を活かすことで、全要素を走査する必要がなくなり、非常に効率的な検索が可能になります。