How to implement interpolation search using recursion

implement interpolation serach
Spread the love

Interpolation search is an algorithm similar to the binary search for searching for a given target value in a sorted array. In this tutorial, I will discuss with you how to implement interpolation search using recursion.

Well, the major condition of this searching algorithm is that your array must be sorted and uniformly distributed. The time complexity of the interpolation searching algorithm is O(log(logn)). This searching algorithm improves the binary search algorithm. The time complexity of the binary search is O(logn). The implementation of the binary search and the interpolation search is the almost same.

The difference between both algorithms is the formula of mid. Let’s see the formula.

mid = low + (val - arr[low]) *(high - low)/(arr[high] - arr[low])

Let’s see the function of this searching algorithm. Don’t worry I will explain you below.

int interpolation_search(int A[], int low, int high, int val)
{
    if (high >= low)
    {
        int mid = (low + ((val - A[low]) * (high - low)) / (A[high] - A[low]));
        if (A[mid] == val)
        {
            return mid;
        }
        else if (A[mid] > val)
        {
            return interpolation_search(A, low, mid, val);
        }
        else if (A[mid] < val)
        {
            return interpolation_search(A, mid + 1, high, val);
        }
    }
    return -1;
}

Well, You can see that this function takes four parameters. The first parameter is an array. And the second parameter is the lower bound of the array. After the third parameter is the upper bound. Well and the last parameter of this function is our value which we have to find from this array.

Well, now you have to check a condition that the high value is greater than or equal to the lower value. After these conditions calculate the mid-value according to our formula. I have already shown you this formula.

Well, now check the index of mid-value is equal to our required value. Well, if this condition has been satisfied then return the mid-value.

Well, if the mid index’s value is greater than our required value then call again this function. Now you have to change the parameters of this function. You have to change the higher bound is equal to mid.

Well, if the mid index value is smaller than our required value then the lower bound will be the mid-value.

Well, Our function recursively calls it again until the high is smaller than the lower. If we don’t get the index of our required value then return -1. That means this value doesn’t exist in this array.

Full Code

#include <bits/stdc++.h>
using namespace std;
int interpolation_search(int A[], int low, int high, int val)
{
    if (high >= low)
    {
        int mid = (low + ((val - A[low]) * (high - low)) / (A[high] - A[low]));
        if (A[mid] == val)
        {
            return mid;
        }
        else if (A[mid] > val)
        {
            return interpolation_search(A, low, mid, val);
        }
        else if (A[mid] < val)
        {
            return interpolation_search(A, mid + 1, high, val);
        }
    }
    return -1;
}
int main()
{
    int A[] = {-8, -1, 5, 9, 10, 17, 18, 25, 36};
    int n = 9;
    int val = -8;
    int pos = interpolation_search(A, 0, n - 1, val);
    cout << pos;
    return 0;
}

Github Link: https://github.com/AR-Shahin/Data_Structure_and_Algorithm/commit/6d3ec796c6a8cf56fcbafdb68c34e5c81c6d2200


Spread the love

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://devshahin.com/

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published.