# C++ Program to Find a Search Sequence using Binary Search

C++ Program to find a search sequence using Binary search.

Problem Description

1. Implement binary search to find the existence of a search sequence in an array.
2. The time complexity of Binary search is O(log(n)).

Problem Solution

1. Implement the binary search to find the first value of search sequence.
2. If it is there, then compare the remaining item sequentially.
3. Otherwise, the sequence is not there.
4. Exit.

Program/Source Code

C++ program to compare Binary and Sequential 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;

// A function implementing Binary search on a sorted array.
int BinarySearch(int a[], int start, int end, int item, int iter)
{
int i, mid;
iter++;
// Assigning middle of the array.
mid = start + (end-start+1)/2;
// If value is less than value at start index more than end index then item is not in the array.
if(item > a[end] || item < a[start] || mid == end)
{
return -1;
}
// Return the mid index.
else if(item == a[mid])
{
return mid;
}
// Return the start index.
else if(item == a[start])
{
return start;
}
// Return the end index.
else if(item == a[end])
{
return end;
}
// According to the item value choose the partion to proceed further.
else if(item > a[mid])
BinarySearch(a, mid, 19, item, iter);
else
BinarySearch(a, start, mid, item, iter);
}

int main()
{
int n, i, flag=0, Bindex, a[20]={1, 9, 18, 24, 27, 35, 38, 41, 49, 53, 55, 66, 67, 72, 75, 77, 81, 89, 90, 97};
cout<<"\nEnter the number of element in the search sequence: ";
cin>>n;
int s[n];
for(i = 0; i < n; i++)
cin>>s[i];

// Get the index of the first value in the search sequence found in data set array.
Bindex = BinarySearch(a, 0, 19, s[0], 0);

if(Bindex == -1)
{
return 0;
}
else
{
// If first value found then check for others sequentially.
for(i = Bindex; i < n+Bindex; i++)
if(a[i] != s[i-Bindex])
flag = 5;

if(flag == 5)
else
cout<<"\nSequence found between index "<<Bindex<<" and "<<Bindex+n<<".";
}

return 0;
}```
Program Explanation

1. Assign the data to the array in a sorted manner.
2. Call BinarySearch() function with ‘arr’ the array of data and ‘n’ the number of values, start and end index, iteration count and s[0] be the element to be searched in the argument list.
3. Increment the iteration counter and compare the item value with the a[mid].
4. If item < a[mid] choose first half otherwise second half to proceed further. 5. Return index value to main. 6. In main(), sequentially compare the remaining items of search sequence to next items in the array. 7. Print the index range of the sequence found. 8. Exit.

Runtime Test Cases
```Case 1:
Enter the number of element in the search sequence: 3
35
38
41

Sequence found between index 5 and 8.

Case 2:
Enter the number of element in the search sequence: 3
35
38
40