इस C++ प्रोग्राम में हम फाइबोनैचि संख्याओं का उपयोग करके डिवाइड एंड कंकर दृष्टिकोण को लागू करते हैं। फाइबोनैचि संख्याओं का उपयोग करके, हम डेटा सरणी के मध्य की गणना करके डेटा आइटम खोजते हैं। इस दृष्टिकोण की समय जटिलता O(log n) है।
एल्गोरिदम
शुरुआत डेटा को सॉर्टेड तरीके से सरणी में निर्दिष्ट करें। खोजे जाने वाले एलिमेंट का इनपुट लें। FibonacciSearch() फ़ंक्शन कॉल करें। 'start+fib[index-2]' एक्सप्रेशन का उपयोग करके मिड मान की गणना करें। यदि चुना गया आइटम मिड इंडेक्स पर मान के बराबर है, तो परिणाम प्रिंट करें और मेन पर लौटें। यदि यह मिड इंडेक्स पर मान से कम है, तो बाएं उप-सरणी के साथ आगे बढ़ें। यदि यह मिड इंडेक्स पर मान से अधिक है, तो दाएं उप-सरणी के साथ आगे बढ़ें। यदि गणना किया गया मिड मान स्टार्ट या एंड के बराबर है तो आइटम सरणी में नहीं मिला। अंत
उदाहरण कोड
#include<iostream> using namespace std; void FibonacciSearch(int *a, int start, int end, int *fib, int index, int item) { int i, mid; mid = start+fib[index-2]; if(item == a[mid]) { cout<<"\n आइटम "<<mid<<" इंडेक्स पर मिला।"; return; } else if(item == a[start]) { cout<<"\n आइटम "<<start<<" इंडेक्स पर मिला।"; return; } else if(item == a[end]) { cout<<"\n आइटम "<<end<<" इंडेक्स पर मिला।"; return; } else if(mid == start || mid == end) { cout<<"\nएलिमेंट नहीं मिला"; return; } else if(item > a[mid]) FibonacciSearch(a, mid, end, fib, index-1, item); else FibonacciSearch(a, start, mid, fib, index-2, item); } main() { int n, i, fib[20], a[10]={3, 7, 55, 86, 7, 15, 26, 30, 46, 95}; char ch; fib[0] = 0; fib[1] = 1; i = 1; while(fib[i] < 10) { i++; fib[i] = fib[i-1] + fib[i-2]; } up: cout<<"\nखोजे जाने वाले एलिमेंट को दर्ज करें: "; cin>>n; FibonacciSearch(a, 0, 9, fib, i, n); cout<<"\n\n\tक्या आप और खोजना चाहते हैं...पसंद दर्ज करें (y/n)?"; cin>>ch; if(ch == 'y' || ch == 'Y') goto up; return 0; } } आउटपुट
खोजे जाने वाले एलिमेंट को दर्ज करें: 26 आइटम 6 इंडेक्स पर मिला। क्या आप और खोजना चाहते हैं...पसंद दर्ज करें (y/n)?y खोजे जाने वाले एलिमेंट को दर्ज करें: 45 आइटम नहीं मिला क्या आप और खोजना चाहते हैं...पसंद दर्ज करें (y/n)?n
