# C++ Program to Search Sorted Sequence using Divide and Conquer

«
»

C++ Program to Search in Sorted Sequence using Divide and Conquer with the aid of Fibonacci Numbers.

Problem Description

1. It implements a Divide and Conquer approach using Fibonacci numbers.
2. Using Fibonacci numbers we calculate mid of data array to search the data item.
3. The time complexity is O(log(n)).

Problem Solution

1. Calculate the mid of the array.
2. Divide the array into two sub-array.
3. Compare the item with mid element and proceed accordingly.
4. Exit.

Program/Source Code

C++ program to implement Fibonacci Search.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

```#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)
{
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, a={1, 9, 18, 24, 27, 35, 38, 41, 49, 53, 55, 66, 67, 72, 75, 77, 81, 89, 90, 97};
char ch;

fab = 0;
fab = 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;
}```
Program Explanation

1. Assign the data to the array in a sorted manner.
2. Take input of the element to be searched.
3. Call FibonacciSearch() function.
4. Calculate the mid value using ‘start+fab[index-2]’ expression.
5. If the item is equal to the value at mid index, print result and return to main.
6. If the item is lesser than the value at mid index, proceed with the left sub-array.
7. If the item is more than the value at mid index, proceed with the right sub-array.
8. If the calculated mid value is equal to either start or end then the item is not found in the array.
10. Exit.

Runtime Test Cases
```Case 1:
Enter the Element to be searched: 38

Item found at 6 index.

Do you want to search more...enter choice(y/n)?y

Enter the Element to be searched: 66

Item found at 11 index.

Do you want to search more...enter choice(y/n)?y

Enter the Element to be searched: 89

Item found at 17 index.

Do you want to search more...enter choice(y/n)?y

Enter the Element to be searched: 1

Item found at 0 index.

Do you want to search more...enter choice(y/n)?y

Enter the Element to be searched: 97

Item found at 19 index.

Do you want to search more...enter choice(y/n)?n```

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms. 