Code:
#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 "<
return;
}
// Return if item found at start index.
else if(item == a[start])
{
cout<<"\nItem found at "<
return;
}
// Return if item found at end index.
else if(item == a[end])
{
cout<<"\nItem found at "<
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;
}
Output:
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
More C++ Programs:
