সি# ব্যবহার করে সারি অনুসারে এবং কলাম অনুসারে বর্ধিত ম্যাট্রিক্সে কীভাবে অনুসন্ধান করবেন?

এই সমস্যার আদিম সমাধান হল প্রদত্ত কী অনুসন্ধান করতে ইনপুট ম্যাট্রিক্সে সংরক্ষিত সমস্ত উপাদান স্ক্যান করা। এই রৈখিক অনুসন্ধান পদ্ধতিতে O(MN) সময় লাগে যদি ম্যাট্রিক্সের আকার MxN হয়।

ম্যাট্রিক্সটিকে একটি সাজানো এক-মাত্রিক অ্যারে হিসাবে দেখা যেতে পারে। যদি ইনপুট ম্যাট্রিক্সের সমস্ত সারি উপরের-নীচের ক্রমে একত্রিত হয় তবে এটি একটি সাজানো এক-মাত্রিক অ্যারে গঠন করে। এবং, সেই ক্ষেত্রে বাইনারি অনুসন্ধান অ্যালগরিদম এই 2D অ্যারের জন্য উপযুক্ত। কোডের নীচের অংশটি একটি ফাংশন SearchRowwiseColumnWiseMatrix বিকাশ করে যা ইনপুট হিসাবে একটি দ্বি-মাত্রিক অ্যারে এবং অনুসন্ধান কী নেয় এবং পাওয়া অনুসন্ধান কীটির সাফল্য বা ব্যর্থতার উপর নির্ভর করে সত্য বা মিথ্যা ফেরত দেয়।

উদাহরণ

public class Matrix{
   public bool SearchRowwiseColumnWiseMatrix(int[,] mat, int searchElement){
      int col = getMatrixColSize(mat);
      int start = 0;
      int last = mat.Length - 1;
      while (start <= last){
         int mid = start + (last - start) / 2;
         int mid_element = mat[mid / col, mid % col];
         if (searchElement == mid_element){
            return true;
         }
         else if (searchElement < mid_element){
            last = mid - 1;
         }
         else{
            start = mid + 1;
         }
      }
      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, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
   Console.WriteLine(m.SearchRowwiseColumnWiseMatrix(mat, 11));
}

আউটপুট

TRUE