#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <ctype.h>

int interpolationsearch (int [], int, int);
void quicksort (int [], int);
int partition(int *,int );

int counter=0;

int main()
{
	int p[500000], i, n, element;
       	 
        	int y;
	time_t seed;
	
	
	time(&seed);
	srand((long)seed);


	printf("Dwse to plithos twn stoixeiwn tou pinaka: ");
	scanf("%d",&n);
	/*for (i=0; i<n; i++)
	{
		printf ("Dose to %do stoixeio: ",i+1);
		scanf("%d",&p[i]);
	}   */

	for (i=0; i<n; i++)		
		p[i] = rand();

	quicksort(p, n);		

	for(i=0; i<n; i++)
		printf("%d: %d\t",i,p[i]);	

	printf("\n\nDwse to stoixeio pou theleis na psaxeis mesa ston pinaka: ");
	scanf("%d",&element);
	
	if((y=binary_interpolation_search(p,n, element))<=0)
	{
		printf("\nTo stoixeio %d den yparxei ston pinaka!\n",element);
	}
	else
	{
		printf ("\nTo stoixeio %d bre8hke sthn 8esh %d.\n",element,y);
	}

	printf("\nEginan %d sygkriseis.\n",counter);

}


int binary_interpolation_search(int p[], int n,int x)
{	
	int low=0;
	int high=n-1;
	int mid;

	while(p[low]<x && p[high]>=x)
	{
		mid=low+((x-p[low])*(high-low))/(p[high]-p[low]);
		counter++;
		if(p[mid]<x)
		{
			low=mid+1;
			
		}
		else if(p[mid]>x)
		{
			high=mid-1;
			
		}
		else
		{	return mid;	}
			
		counter =counter+2;
	}

	counter++;
	if(p[low]==x)
	{	return low+1;	}
	else
	{	return -1;		}

}



void quicksort(int *p,int n)
{
        int a;
if(n>1)
{
        a=partition(p,n);

        quicksort(p,a);

        quicksort(p+a,n-a);
}

return;
}



int partition(int *p,int n)
{
int *p1,*p2,temp;
for(p1=p-1,p2=p+n; ;)
{
        do
        {	
                ++p1;
                
        }while(*p1<*p);

        do
        {	
                --p2;
        	        
        }while(*p2>*p);
        
        if(p1<p2)
        {		
                temp=*p1;
                *p1=*p2;
                *p2=temp;
        } 
        else
                break;
	
}
                
return (int) (p2-p+1);

}