Cách tìm kiếm trong ma trận tăng theo hàng trong C#

Giải pháp nguyên thủy quét toàn bộ ma trận O(M×N). Cách tối ưu: bắt đầu từ góc trên bên phải. Nếu phần tử tìm kiếm lớn hơn phần tử hiện tại → tăng hàng (dòng), ngược lại giảm cột. Hàm SearchRowwiseIncrementedMatrix nhận ma trận 2D và khóa tìm kiếm, trả về true/false.

Code

public class Matrix
{
    public bool SearchRowwiseIncrementedMatrix(int[,] mat, int searchElement)
    {
        int row = mat.GetLength(0);
        int col = mat.GetLength(1) - 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;
    }
}

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)); // Output: True
}

Kết quả đầu ra

True

Điều kiện: Mỗi hàng tăng dần, và phần tử đầu hàng sau lớn hơn phần tử cuối hàng trước.