सी प्रोग्राम में फ्लोटिंग पॉइंट अंकगणित का उपयोग किए बिना परिमेय संख्याओं के लिए द्विआधारी खोज

इस समस्या में, हमें परिमेय संख्याओं की एक क्रमबद्ध सारणी दी गई है। और हमें फ्लोटिंग पॉइंट अंकगणित का उपयोग किए बिना इस तर्कसंगत संख्या सरणी के लिए बाइनरी सर्च एल्गोरिदम का उपयोग करके दिए गए तत्व को खोजना होगा।

एक परिमेय संख्या संख्या को 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