การค้นหาในเมทริกซ์ที่เพิ่มขึ้นทั้งแถวและคอลัมน์ใน C#

วิธีแก้ปัญหาแบบดั้งเดิมคือสแกนทุกองค์ประกอบ ใช้เวลา O(MN) เมทริกซ์สามารถมองเป็นอาร์เรย์ 1 มิติที่เรียงลำดับได้ หากต่อแถวทั้งหมดจากบนลงล่าง จะได้อาร์เรย์ 1 มิติที่เรียงลำดับ จึงสามารถใช้ Binary Search ได้ โค้ดด้านล่างพัฒนาฟังก์ชัน SearchRowwiseColumnWiseMatrix ใช้ Binary Search บนเมทริกซ์ 2 มิติ

ตัวอย่างโค้ด

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

ผลลัพธ์

True