Users Online

· Guests Online: 40

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads
No Threads created
Hottest Threads
No Threads created

Latest Articles

Interpolation Search Algorithm in C++

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.

 

Comments

No Comments have been Posted.

Post Comment

Please Login to Post a Comment.

Ratings

Rating is available to Members only.

Please login or register to vote.

No Ratings have been Posted.
Render time: 0.72 seconds
10,272,941 unique visits