C#で行ごと・列ごとにソートされた行列を効率的に検索する方法

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

しかし、この行列は「ソート済みの1次元配列」とみなすことができます。実際、入力行列のすべての行を上から下の順に連結すると、昇順に並んだ1次元配列が形成されます。そのため、この2次元配列に対しては二分探索（バイナリサーチ）アルゴリズムを適用するのが最適です。

以下のコードでは、2次元配列と検索キーを引数として受け取り、検索の成功・失敗に応じて true または false を返すメソッド SearchRowwiseColumnWiseMatrix を実装しています。ポイントは、1次元的なインデックス mid を mid / col（行番号）と mid % col（列番号）に変換することで、2次元配列の任意の要素に直接アクセスできる点です。

コード例

public class Matrix{
   public bool SearchRowwiseColumnWiseMatrix(int[] mat, int searchElement){
      int col = getMatrixColSize(mat);
      int start = 0;
      int last = mat.Length - 1;
      while (start <= last){
         int mid = start + (last - start) / 2;
         int mid_element = mat[mid / col, mid % col];
         if (searchElement == mid_element){
            return true;
         }
         else if (searchElement < mid_element){
            last = mid - 1;
         }
         else{
            start = mid + 1;
         }
      }
      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, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
   Console.WriteLine(m.SearchRowwiseColumnWiseMatrix(mat, 11));
}

出力結果

TRUE

この実装により、時間計算量は O(log(MN)) まで削減されます。線形探索の O(MN) と比較して大幅に高速化されており、行ごと・列ごとにソートされた大規模な行列からも、目的の要素を短時間で見つけ出すことが可能です。