การค้นหาในเมทริกซ์ที่เพิ่มขึ้นตามแถว (Row-wise Sorted Matrix) ใน C#

วิธีแก้ปัญหาแบบดั้งเดิมคือสแกนทุกองค์ประกอบในเมทริกซ์เพื่อค้นหาคีย์ที่กำหนด วิธี Linear Search ใช้เวลา O(MN) หากขนาดเมทริกซ์คือ MxN

เมทริกซ์ต้องสแกนจากมุมขวาบน หากค่าที่ค้นหามากกว่าค่ามุมขวาบน ให้เพิ่มแถว (Row++) มิฉะนั้นลดคอลัมน์ (Col--) โค้ดด้านล่างพัฒนาฟังก์ชัน SearchRowwiseIncrementedMatrix ที่รับอาร์เรย์ 2 มิติและคีย์ค้นหา คืนค่า true หรือ false

โค้ด

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

ผลลัพธ์

True