এই সমস্যাতে, আমাদের একটি সর্টেড রেশনাল নম্বরের অ্যারে দেওয়া থাকে। এবং আমাদের বাইনারি সার্চ অ্যালগরিদম ব্যবহার করে দেওয়া এলিমেন্টটি খুঁজে বের করতে হবে, কিন্তু ফ্লোটিং পয়েন্ট অ্যারিথমেটিক ব্যবহার ছাড়া।
রেশনাল নম্বর হলো 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
