Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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

Function Documentation

◆ InterpolationSearch()

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

function to search the value in an array using interpolation search

Parameters
[in]arrarray to search in
[in]valuevalue to search for
[in]lenlength of array
Returns
index where the value is found
-1 if not found
15  {
16  int low = 0;
17  int high = n - 1;
18  while (low <= high) {
19  int mid = low + (((high - 1) * (x - A[low])) / (A[high] - A[low]));
20  if (x == A[mid])
21  return mid; // Found x, return (exit)
22  else if (x < A[mid])
23  high = mid - 1; // X lies before mid
24  else
25  low = mid + 1; // x lies after mid
26  }
27 
28  return -1;
29 }

◆ main()

int main ( void  )

main function

< passed array A inside the InterpolationSearch function

32  {
33  int A[] = {2, 4, 5, 7, 13, 14, 15, 23};
34  int x = 17;
35 
36  ///< passed array A inside the InterpolationSearch function
37  int index = InterpolationSearch(A, 8, x);
38  if (index < 0)
39  std::cout << "Number " << x << " not found" << std::endl;
40  else
41  std::cout << "Number " << x << " is at " << index << std::endl;
42 }
Here is the call graph for this function:
std::cout
std::endl
T endl(T... args)
InterpolationSearch
int InterpolationSearch(int A[], int n, int x)
Definition: interpolation_search2.cpp:15