# Interpolation Search Algorithm In C++

In this tutorial, we will learn how to implement Interpolation Search in C++ with the algorithm.

## What is Interpolation Search?

You must be knowing several searching algorithms. In this tutorial, we are going to discuss about Interpolation Search in C++. We apply this Interpolation Search Algorithm into an array which is sorted. It is an improvement over Binary Search. Interpolation search may go to different locations according to the value of the key we are searching. For example, if the value of the key is near to the last element, Interpolation Search Algorithm is likely to start search toward the end side.

To find the position that we have to search, it uses the following formula:

pos = st + [ (x – array[st])*(end – st) / (array[end] – array[st]) ]

array[] : Array where elements need to be searched x : Element to be searched st : Starting index in array[] end : Ending index in array[]

**C++ program for interpolation search implementation**

#include<bits/stdc++.h> using namespace std; int interpolation_search(int array[], int num, int x) { // Find indexes of two corners int st = 0, end = (num - 1); while (st <= end && x >= array[st] && x <= array[end]) { if (st == end) { if (array[st] == x) return st; return -1; } int pos = st + (((double)(end - st) / (array[end] - array[st])) * (x - array[st]); if (array[pos] == x) return pos; // If x is larger, x is in upper part if (array[pos] < x) st = pos + 1; // If x is smaller, x is in the lower part else end = pos - 1; } return -1; } // Driver Code int main() { int array[] = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47}; int num = sizeof(array)/sizeof(array[0]); int x = 18; //This is the element you want to search int index = interpolation_search(arr, n, x); // If element was found if (index != -1) cout << "Element found at index " << index; else cout << "Element not found."; return 0; }

Output: Element found at index 4

If there is uniform distribution among elements, then interpolation search algorithm’s complexity can be upto **O (log log n))**. In the worst case, it can take upto O(n).

**Explanation of my code:**

- I have created a function which may seem complex looking at first but it is very simple.
- I have passed an
**array**,**num**and**x**as arguments in the function. - Here array is the given array of elements,
**num**is the size of array and**x**is value to search. - Now let’s talk about inside of the function. Starting index is equal to 0 and ending index is equal to size -1.
- Now if there is only one element in array i.e
**st=end,**and the present element is**x**, we will return the index else goto 5. - If 4 is not fulfilled, we will search by using the formula given above.
- If the element is at the index computed using the formula
**pos**, return the index position**pos**else goto 7. - Make the starting index
**pos+1,**if element at**pos**is less than**x**else goto 9. - Make the ending position as
**pos-1,**if element at**pos**is greater than**x.** - Next, there is main() program to test the given code.

Prerequisite is a **Binary search.**

For any queries, post your doubts in comments.

## Leave a Reply