Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
interpolation_search.cpp File Reference

Interpolation search algorithm More...

#include <iostream>
Include dependency graph for interpolation_search.cpp:

Functions

int interpolation_search (int arr[], int value, int len)
 
int main ()
 

Detailed Description

Function Documentation

◆ interpolation_search()

int interpolation_search ( int  arr[],
int  value,
int  len 
)

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
0 if not found
15  {
16  int low = 0, high, mid;
17  high = len - 1;
18 
19  while (arr[low] <= value && arr[high] >= value) {
20  mid = (low +
21  ((value - arr[low]) * (high - low)) / (arr[high] - arr[low]));
22  if (arr[mid] > value)
23  high = mid - 1;
24  else if (arr[mid] < value)
25  low = mid + 1;
26  else
27  return mid;
28  }
29 
30  if (arr[low] == value)
31  return low;
32 
33  return -1;
34 }

◆ main()

int main ( void  )

main function

37  {
38  int n, value, re;
39 
40  std::cout << "Enter the size of array(less than 100) : ";
41  std::cin >> n;
42 
43  int *array = new int[n];
44 
45  std::cout << "array in ascending (increasing) order : " << std::endl;
46 
47  for (int i = 0; i < n; i++) std::cin >> array[i];
48 
49  std::cout << "Enter the value you want to search : ";
50  std::cin >> value;
51 
52  re = interpolation_search(array, value, n);
53 
54  if (re == -1)
55  std::cout << "Entered value is not in the array" << std::endl;
56  else
57  std::cout << "The value is at the position " << re << std::endl;
58 
59  delete[] array;
60  return 0;
61 }
Here is the call graph for this function:
std::cout
std::endl
T endl(T... args)
interpolation_search
int interpolation_search(int arr[], int value, int len)
Definition: interpolation_search.cpp:15
std::cin