C++ Programming Code Examples

C++ > Sorting Searching Code Examples

Program to Implement a Binary Search Algorithm for a Specific Search Sequence



Program to Implement a Binary Search Algorithm for a Specific Search Sequence

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

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

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

C++ program to compare Binary and Sequential Search.

#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)
	{
		cout<<"\nNot found";
		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]={3, 9, 22, 74, 19, 33, 28, 49, 44, 43, 18, 23, 69, 96, 88, 77, 14, 11, 8, 83};
	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)
	{
		// if return index is -1 then not found.
		cout<<"\nNot found.";
		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)
			cout<<"\nNot found.";
		else
			cout<<"\nSequence found between index "<<Bindex<<" and "<<Bindex+n<<".";
	}
 
	return 0;
}