fork(2) download
copy 
  1. #include <stdio.h>
  2.  
  3. // find out if a target x exists in the sorted array A
  4. // or not using Interpolation search algorithm
  5. int InterpolationSearch(int A[], int n, int x)
  6. {
  7.     // search space is A[low..high]
  8.     int low = 0, high = n - 1, mid;
  9.  
  10.     while (A[high] != A[low] && x >= A[low] && x <= A[high])
  11.     {
  12.         // estimate mid
  13.         mid = low + ((x - A[low]) * (high - low) / (A[high] - A[low]));
  14.  
  15.         // target value is found
  16.         if (x == A[mid])
  17.             return mid;
  18.  
  19.         // discard all elements in the right search space
  20.         // including the mid element
  21.         else if (x < A[mid])
  22.             high = mid - 1;
  23.  
  24.         // discard all elements in the left search space
  25.         // including the mid element
  26.         else
  27.             low = mid + 1;
  28.     }
  29.  
  30.     // if target is found
  31.     if (x == A[low])
  32.         return low ;
  33.  
  34.     // x doesn't exist in the array
  35.     else
  36.         return -1;
  37. }
  38.  
  39. // Interpolation search algorithm
  40. int main(void)
  41. {
  42.     int A[] = {2, 5, 6, 8, 9, 10};
  43.     int target = 5;
  44.  
  45.     int n = sizeof(A)/sizeof(A[0]);
  46.     int index = InterpolationSearch(A, n, target);
  47.  
  48.     if (index != -1)
  49.         printf("Element found at index %d", index);
  50.     else
  51.         printf("Element not found in the array");
  52.  
  53.     return 0;
  54. }
Success #stdin #stdout 0s 4336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Element found at index 1
https://ideone.com/5nI5QI
Interpolation search algorithm
language:
C (gcc 8.3)
created:
6 years ago
visibility:
secret

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!