সি প্রোগ্রামে ফ্লোটিং পয়েন্ট পাটিগণিত ব্যবহার না করে মূলদ সংখ্যার জন্য বাইনারি অনুসন্ধান করুন

এই সমস্যায়, আমাদের মূলদ সংখ্যাগুলির একটি সাজানো অ্যারে দেওয়া হয়েছে। এবং আমাদের ফ্লোটিং পয়েন্ট গাণিতিক ব্যবহার না করে এই মূলদ সংখ্যা অ্যারের জন্য বাইনারি অনুসন্ধান অ্যালগরিদম ব্যবহার করে প্রদত্ত উপাদানটি অনুসন্ধান করতে হবে৷

একটি মূলদ সংখ্যা সংখ্যা হল p/q আকারে উপস্থাপিত যেখানে p এবং q উভয়ই পূর্ণসংখ্যা। উদাহরণস্বরূপ, ⅔, ⅕.

বাইনারী অনুসন্ধান এটি অনুসন্ধানের কৌশল যা উপাদান খুঁজে পাওয়ার জন্য অ্যারের মাঝখানে খুঁজে বের করে কাজ করে।

মূলদ সংখ্যার একটি সাজানো অ্যারে থেকে বাইনারি অনুসন্ধান ব্যবহার করে উপাদান খুঁজে বের করার জন্য, যেখানে ফ্লোটিং পয়েন্ট পাটিগণিত অনুমোদিত নয়। কোন উপাদানটি বৃহত্তর বা কোনটি পাওয়া যাবে তা খুঁজে বের করার জন্য আমরা লব এবং হরগুলির তুলনা করব৷

উদাহরণ

এর জন্য একটি প্রোগ্রাম তৈরি করা যাক,

#include <stdio.h>
struct Rational {
   int p;
   int q;
};
int compare(struct Rational a, struct Rational b) {
   if (a.p * b.q == a.q * b.p)
      return 0;
   if (a.p * b.q > a.q * b.p)
      return 1;
   return -1;
}
int binarySearch(struct Rational arr[], int l, int r, struct Rational x) {
   if (r >= l) {
      int mid = l + (r - l)/2;
   if (compare(arr[mid], x) == 0) return mid;
   if (compare(arr[mid], x) > 0)
      return binarySearch(arr, l, mid-1, x);
   return binarySearch(arr, mid+1, r, x);
   }
   return -1;
}
int main() {
   struct Rational arr[] = {{1, 4}, {2, 3}, {3, 2}, {7, 2}};
   struct Rational x = {3, 2};
   int n = sizeof(arr)/sizeof(arr[0]);
   printf("Element found at index %d", binarySearch(arr, 0, n-1, x));
}

আউটপুট

Element found at index 2