समस्या विवरण
हमें एक क्रमबद्ध सरणी दी जाती है जिसमें परिमेय संख्याएं (p/q रूप में) होती हैं। हमें दिए गए तत्व को बाइनरी खोज का उपयोग करके ढूंढना है, लेकिन फ्लोटिंग पॉइंट अंकगणित का उपयोग किए बिना।
परिमेय संख्या क्या है?
परिमेय संख्या p/q रूप में व्यक्त एक संख्या है जहां p और q पूर्णांक हैं (q ≠ 0)। उदाहरण: ⅔, ⅕, ¾।
तुलना रणनीति
दो परिमेय संख्याओं a = p1/q1 और b = p2/q2 की तुलना करने के लिए:
p1 × q2औरp2 × q1की तुलना करें- यदि
p1×q2 = p2×q1→ बराबर - यदि
p1×q2 > p2×q1→ a बड़ा है - अन्यथा → b बड़ा है
C प्रोग्राम
#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("तत्व इंडेक्स %d पर मिला", binarySearch(arr, 0, n - 1, x));
return 0;
}
आउटपुट
तत्व इंडेक्स 2 पर मिला
मुख्य लाभ
- सटीकता: फ्लोटिंग-पॉइंट त्रुटियों से पूरी तरह बचा जाता है
- दक्षता: O(log n) समय जटिलता
- सटीकता: पूर्णांक अंकगणित का उपयोग करके सटीक तुलना
सावधानियां
- सरणी क्रमबद्ध होनी चाहिए
- ओवरफ्लो से बचने के लिए
long longका उपयोग करें यदि अंश/हर बड़े हैं - हर (q) शून्य नहीं होना चाहिए
