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

Ma trận có thể xem như mảng 1D đã sắp xếp nếu nối các hàng theo thứ tự từ trên xuống. Do đó dùng Binary Search trên ma trận 2D. Hàm SearchRowwiseColumnWiseMatrix nhận ma trận 2D và khóa tìm kiếm, trả về true/false.

Ví dụ

public class Matrix
{
    public bool SearchRowwiseColumnWiseMatrix(int[,] mat, int searchElement)
    {
        int cols = mat.GetLength(1);
        int start = 0;
        int end = mat.Length - 1;
        while (start <= end)
        {
            int mid = start + (end - start) / 2;
            int midElement = mat[mid / cols, mid % cols];
            if (searchElement == midElement)
            {
                return true;
            }
            else if (searchElement < midElement)
            {
                end = mid - 1;
            }
            else
            {
                start = mid + 1;
            }
        }
        return false;
    }
}

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

Kết quả đầu ra

True

Điều kiện: Mỗi hàng tăng dần, mỗi cột 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.