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; }