#include <iostream>
#include <math.h>
using namespace std;
bool interpolation_search(int array[], int array_size, int value)
{
    int iteracje=0;
    int Low = 0;
    int Hi = array_size-1;
    while (Low<=Hi and iteracje<=sqrt(Hi))
    {
        int mid = Low + ((Hi - Low)*(value - array[Low])) / (array[Hi] - array[Low]);
        iteracje++;
        if (array[mid]==value)
        {
            cout << "Liczba iteracji = " << iteracje << " ";
            cout << "Wynik = true";
            return true;
        }
        if (array[mid] > value)
        {
            Hi=(mid-1);
        }
        if (array[mid] < value)
        {
            Low=(mid+1);
        }
    }
    cout << "Liczba iteracji = " << iteracje << " ";
    cout << "Wynik = false";
    return false;
}
int main ()
{
    int array_size;
    int value;
    int array[20];
    cout << "Podaj rozmiar tablicy: ";
    cin >> array_size;
    if (array_size>=21 or array_size<=0)
    {
        cout << "Rozmiar tablicy powinien byc wiekszy od 0 i mniejszy od 21!";
        return 0;
    }
    cout << "Podaj elementy tablicy: ";
    for (int i=0;i<array_size;i++)
    {
        cin >> array[i];
        if (array[i]<array[i-1])
        {
            cout << "Elementy tablicy nie sa posortowane!";
            return 0;
        }
    }
    cout << "Podaj szukana wartosc: ";
    cin >> value;
    interpolation_search(array, array_size, value);
    return 0;
}