C++ Programming Code Examples

C++ > Sorting Searching Code Examples

C++ Program to Implement Interpolation Search Algorithm

C++ Program to Implement Interpolation Search Algorithm

- It is a better approach for uniform data.
- Implement binary search using interpolation approach.
- The time complexity is O(log(n)).

- Implement the binary search on a sorted array.
- Calculate mid value using interpolation formula.
- Exit.

#include<iostream>
 
using namespace std;
 
// A function implementing Interpolation search on a sorted array.
void InterpolationSearch(int a[], int start, int end, int item)
{
	int mid;
 
	// Assigning middle of the array.
	mid = start+((item-a[start])*(end-start))/(a[end]-a[start]);
 
	if(item == a[mid])
	{
		cout<<"\nItem found at "<<mid<<" index.";
		return;
	}
	// Return if item found at start index.
	else if(item == a[start])
	{
		cout<<"\nItem found at "<<start<<" index.";
		return;
	}
	// Return if item found at end index.
	else if(item == a[end])
	{
		cout<<"\nItem found at "<<end<<" index.";
		return;
	}
	else if(mid == start || mid == end)
	{
		cout<<"\nElement not found";
		return;
	}
	// According to the item value choose the partition to proceed further.
	else if(item > a[mid])
		InterpolationSearch(a, mid, 19, item);
	else
		InterpolationSearch(a, start, mid, item);
}
 
int main()
{
	int n, i, biter, a[20]={1, 4, 28, 44, 88, 76, 47, 99, 33, 62, 24, 13, 74, 84, 19, 86, 63, 77, 48, 23};
	char ch;
 
	up:
	cout<<"\nEnter the Element to be searched: ";
	cin>>n;
	// Implement Interpolation search.
	InterpolationSearch(a, 0, 19, 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;
}