interpolation_search2.cpp File Reference

Interpolation search algorithm More...

#include <iostream>

Include dependency graph for interpolation_search2.cpp:

Functions
int	InterpolationSearch (int A[], int n, int x)
int	main ()

Detailed Description

Interpolation search algorithm

Function Documentation

InterpolationSearch()

int InterpolationSearch	(	int	A[],
		int	n,
		int	x
	)

function to search the value in an array using interpolation search

Parameters

[in]	arr	array to search in
[in]	value	value to search for
[in]	len	length of array

Returns

index where the value is found

-1 if not found

                                               {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + (((high - 1) * (x - A[low])) / (A[high] - A[low]));
        if (x == A[mid])
            return mid;  // Found x, return (exit)
        else if (x < A[mid])
            high = mid - 1;  // X lies before mid
        else
            low = mid + 1;  // x lies after mid
    }
 
    return -1;
}

main()

int main

(

void

)

main function

< passed array A inside the InterpolationSearch function

           {
    int A[] = {2, 4, 5, 7, 13, 14, 15, 23};
    int x = 17;
 
    ///< passed array A inside the InterpolationSearch function
    int index = InterpolationSearch(A, 8, x);
    if (index < 0)
        std::cout << "Number " << x << " not found" << std::endl;
    else
        std::cout << "Number " << x << " is at " << index << std::endl;
}

Here is the call graph for this function: