fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int interpolationSearch(vector<int> arr, int lo, int hi, int x)
  5. {
  6.     int pos;
  7.     if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
  8.         pos = lo
  9.               + (((double)(hi - lo) / (arr[hi] - arr[lo]))
  10.                  * (x - arr[lo]));
  11.         if (arr[pos] == x)
  12.             return pos;
  13.         if (arr[pos] < x)
  14.             return interpolationSearch(arr, pos + 1, hi, x);
  15.         if (arr[pos] > x)
  16.             return interpolationSearch(arr, lo, pos - 1, x);
  17.     }
  18.     return -1;
  19. }
  20. int main()
  21. {
  22.     int n; cin >> n;
  23.     vector<int> a(n);
  24.     for(int i=0; i<n; i++){
  25.         cin >> a[i];
  26.     }
  27.     cout << interpolationSearch(a, 0, n-1, 4);
  28. }
  29.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
5
1 2 3 4 5
stdout
copy 
3
https://ideone.com/Dzh97F
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!