सी # का उपयोग करके पंक्तिवार बढ़ी हुई मैट्रिक्स में कैसे खोजें?

इस समस्या का मूल समाधान इनपुट मैट्रिक्स में संग्रहीत सभी तत्वों को स्कैन करके दी गई कुंजी की खोज करना है। यदि मैट्रिक्स का आकार MxN है, तो इस रैखिक खोज दृष्टिकोण में O(MN) समय लगता है।

मैट्रिक्स को ऊपर दाईं ओर से स्कैन करने की आवश्यकता है, यदि खोज तत्व शीर्ष दाएं तत्व से बड़ा है तो पंक्ति को बढ़ाता है या फिर कॉलम को घटाता है। नीचे दिया गया कोड एक फ़ंक्शन SearchRowwiseIncrementedMatrix विकसित करता है जो इनपुट के रूप में एक द्वि-आयामी सरणी और खोज कुंजी लेता है और खोज कुंजी की सफलता या विफलता के आधार पर सही या गलत लौटाता है।

कोड

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

आउटपुट

TRUE