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

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

행렬은 정렬된 1차원 배열로 볼 수 있습니다. 입력 행렬의 모든 행이 하향식 순서로 연결되면 정렬된 1차원 배열을 형성합니다. 그리고 이 경우 이진 탐색 알고리즘이 이 2D 배열에 적합합니다. 아래 코드는 2차원 배열과 검색 키를 입력으로 받아 검색 키의 성공 또는 실패에 따라 true 또는 false를 반환하는 SearchRowwiseColumnWiseMatrix 함수를 개발합니다.

예시

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