Interpolation Search Algorithm in C++

C++ Program to implement Interpolation Search.

Problem Description

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

Problem Solution

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

Program/Source Code

C++ program to implement Interpolation 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 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, 9, 18, 24, 27, 35, 38, 41, 49, 53, 55, 66, 67, 72, 75, 77, 81, 89, 90, 97};
	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;
}
Program Explanation

1. Assign the data to the array in a sorted manner.
2. Take the input of the element to be searched.
3. Call InterpolationSearch() function.
4. Calculate mid value using ‘start+((item-a[start])*(end-start))/(a[end]-a[start])’ expression.
5. If the item is equal to the value at mid index, print result and return to main.
6. If the item is lesser than the value at mid index, proceed with the left sub-array.
7. If the item is more than the value at mid index, proceed with the right sub-array.
8. If the calculated mid value is equal to either start or end then the item is not found in the array.
9. Return to main and ask for user’s choice to search more.
10. Exit.

advertisement
advertisement
Runtime Test Cases
Case 1:
Enter the Element to be searched: 53
 
Item found at 9 index.
 
        Do you want to search more...enter choice(y/n)?y
 
Enter the Element to be searched: 77
 
Item found at 15 index.
 
        Do you want to search more...enter choice(y/n)?y
 
Enter the Element to be searched: 24
 
Item found at 3 index.
 
        Do you want to search more...enter choice(y/n)?y
 
Enter the Element to be searched: 91
 
Element not found
 
        Do you want to search more...enter choice(y/n)?n

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

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.