C++ Program of Binary Search Using Templates

In this post, we will discuss binary search algorithm implementation using function templates in C++.

If you don’t know how binary search works, then read Binary Search Algorithm.

Program of Binary Search Using Templates

#include<iostream>
using namespace std;

// binary search function using template
// n: size of arr
// x: value to search
// the fucntion returns -1 if x is not found in arr
// otherwise it returns index of x
template<typename T>
int binary_search(T arr[],int n,T x)
{
	int start = 0;
	int end = n-1;
	while(start<=end)
	{
		int mid = (start+end)/2;
		if(arr[mid]==x)	
			return mid;
		else if(arr[mid]<x)	
			start = mid + 1;
		else	
			end = mid - 1;
	}
	return -1;
}

// Template function to print array
// n: size of arr
template<typename T>
void PrintArray(T arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << "\n\n";
}

int main()
{

    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ,12 };
    int n = sizeof(arr) / sizeof(int);

    cout << "Array : " << endl;
    PrintArray(arr, n);
    
    int x, index;
    cout<<"Enter value you want to Search: ";
    cin>>x;
    
    index = binary_search(arr, n, x);
    
    if(index==-1)
    	cout<<x<<" is not present in the array"<<endl;
    else
    	cout<<x<<" is present in the array at position "<<index<<endl;

}

Output

Program of Binary Search Using Templates (recursive)

#include<iostream>
using namespace std;

// binary search function using template
// [start,end] is the range in which we are searching x
// the fucntion returns -1 if x is not found in arr
// otherwise it returns index of x
template<typename T>
int binary_search(T arr[],int start,int end,T x)
{
	if(start<=end)
	{
		int mid = (start+end)/2;
		if(arr[mid]==x)	
			return 	mid;
		else if(arr[mid]<x)	
			return 	binary_search(arr,mid+1,end,x);
		else	
			return	binary_search(arr,start,end-1,x);
	}
	return -1;
}

// Template function to print array
// n: size of arr
template<typename T>
void PrintArray(T arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << "\n\n";
}

int main()
{

    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ,12 };
    int n = sizeof(arr) / sizeof(int);

    cout << "Array : " << endl;
    PrintArray(arr, n);
    
    int x, index;
    cout<<"Enter value you want to Search: ";
    cin>>x;
    
    index = binary_search(arr, 0, n, x);
    
    if(index==-1)
    	cout<<x<<" is not present in the array"<<endl;
    else
    	cout<<x<<" is present in the array at position "<<index<<endl;

}

Output

Read
Find all subsets of an array
Program to count prime numbers in given range
Matrix Multiplication (Recursive)