fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. int interpolationSearch(int arr[], int n, int x) {
  4.     int left = 0, right = n - 1;
  5.  
  6.     while (left <= right && x >= arr[left] && x <= arr[right]) {
  7.         if (left == right) {
  8.             if (arr[left] == x) return left;
  9.             return -1;
  10.         }
  11.  
  12.         int pos = left + ((x - arr[left]) * (right - left)) / (arr[right] - arr[left]);
  13.  
  14.         if (arr[pos] == x) return 1;
  15.         if (arr[pos] < x) left = pos + 1;
  16.         else right = pos - 1;
  17.     }
  18.     return -1;
  19. }
  20.  
  21. int main() {
  22. 	int n,target;
  23. 	cin >> n >> target;
  24. 	int a[n];
  25. 	for(int i = 0;i<n;i++){
  26. 		cin >> a[i];
  27. 	}
  28.    int result = interpolationSearch(a, n, target);
  29.    if(result==1) cout << "FOUND";
  30.    else cout << "NOT FOUND";
  31.  
  32.    return 0;
  33. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
6 5
1 2 3 4 5 6
stdout
copy 
FOUND
https://ideone.com/1r1wMy
language:
C++ (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!