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

«

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
advertisement

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)
	{
		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]={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)
	{
		// 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;
}
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
advertisement
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
 
Not found.

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

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn