#include <stdio.h>
#include <math.h>
#define LENGTH 20


int interpolationSuche (int key, int* values)
{
    int x=0;
    int l=0;
    int r=LENGTH-1;
    while (values[x]!=key)
           {
                x=l+((key-values[l])/(values[r]-values[l]))*(r-l);
                 if( values[x] == key)
                 {
                     return x;
                 }

                 else if (values[x] >= key)
                 {
                      l++;
                 }

                 else if (values[x] <=key)
                 {
                      r--;
                 }
         }
}
int main()
{
    int Zahl;
    int position;
    int array[20]={2,3,9,13,23,33,45,50,51,67,78,80,94,100,102,116,121,169,198,200};
    printf("Geben Sie die Zahl ein, die Sie suchen\n");

    scanf("%d", &Zahl);

    position = interpolationSuche ( Zahl, array);

    printf("Ihre %d Zahl befindet sich an Stelle %d", Zahl,position);

    system("pause");
}