C++ Programming Code Examples C++ > Sorting Searching Code Examples Search Sorted Sequence Using Divide and Conquer with the Aid of Fibonacci Numbers Search Sorted Sequence Using Divide and Conquer with the Aid of Fibonacci Numbers - It implements a Divide and Conquer approach using Fibonacci numbers. - Using Fibonacci numbers we calculate mid of data array to search the data item. - The time complexity is O(log(n)). - Calculate the mid of the array. - Divide the array into two sub-array. - Compare the item with mid element and proceed accordingly. - Exit. C++ program to implement Fibonacci Search. #include<iostream> using namespace std; void FibonacciSearch(int *a, int start, int end, int *fab, int index, int item) { int i, mid; // Assigning middle of the array using Fibonacci element. mid = start+fab[index-2]; // Return if item found at mid index. if(item == a[mid]) { cout<<"\n item found at "<<mid<<" index."; return; } // Return if item found at start index. else if(item == a[start]) { cout<<"\n item found at "<<start<<" index."; return; } // Return if item found at end index. else if(item == a[end]) { cout<<"\n item found at "<<end<<" index."; return; } // If mid becomes start or end of the sub-array then element not found. else if(mid == start || mid == end) { cout<<"\nElement not found"; return; } // According to the item value choose the partion to proceed further. else if(item > a[mid]) FibonacciSearch(a, mid, end, fab, index-1, item); else FibonacciSearch(a, start, mid, fab, index-2, item); } main() { int n, i, biter, fab[20], a[20]={2, 9, 19, 23, 25, 36, 39, 43, 49, 57, 59, 66, 69, 74, 75, 77, 88, 89, 96, 97}; char ch; fab[0] = 0; fab[1] = 1; i = 1; while(fab[i] < 20) { i++; fab[i] = fab[i-1]+fab[i-2]; } up: cout<<"\nEnter the Element to be searched: "; cin>>n; // Implement Fibonacci search. FibonacciSearch(a, 0, 19, fab, i, n); // Ask user to enter choice for further searching. cout<<"\n\n\tDo you want to search more...enter choice(y/n)?"; cin>>ch; if(ch == 'y' || ch == 'Y') goto up; return 0; }