Làm thế nào để tìm kiếm trong một hàng ma trận tăng khôn ngoan bằng cách sử dụng C #?

Giải pháp ban đầu cho vấn đề này là quét tất cả các phần tử được lưu trữ trong ma trận đầu vào để tìm kiếm khóa đã cho. Phương pháp tìm kiếm tuyến tính này tốn O (MN) thời gian nếu kích thước của ma trận là MxN.

Ma trận cần được quét từ trên cùng bên phải, nếu phần tử tìm kiếm lớn hơn phần tử trên cùng bên phải thì tăng hàng hoặc giảm cột. Đoạn mã dưới đây phát triển một hàm SearchRowwiseIncrementedMatrix lấy mảng hai chiều và khóa tìm kiếm làm đầu vào và trả về true hoặc false tùy thuộc vào sự thành công hay thất bại của khóa tìm kiếm được tìm thấy.

Mã

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));
}

Đầu ra

TRUE