C#을 사용하여 행별 증가 행렬에서 검색하는 방법은 무엇입니까?

이 문제에 대한 기본 솔루션은 입력 행렬에 저장된 모든 요소를 ​​스캔하여 주어진 키를 검색하는 것입니다. 이 선형 탐색 방식은 행렬의 크기가 MxN인 경우 O(MN) 시간이 소요됩니다.

행렬은 오른쪽 상단에서 스캔해야 합니다. 검색 요소가 오른쪽 상단 요소보다 크면 행이 증가하고 그렇지 않으면 열이 감소합니다. 아래 코드는 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