#include <stdio.h>
#include <stdlib.h>

void Binary_Search (int [], int, int, int);
void quicksort (int [], int);

int counter=0;

int main()
{
	int input[500000], i, n, element;
	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",&input[i]);
	}*/

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

	quicksort(input, n);		

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

	printf("\n\nDwse to stoixeio pou theleis na psaxeis mesa ston pinaka: ");
	scanf("%d",&element);
	
	Binary_Search(input, element, 0, n-1);

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

}


void Binary_Search (int array[], int x, int left, int right)
{
	int position;	
	
	position = (left + right)/2;	
	
	counter++;
	while (x!=array[position] && right>=left)
	{
		counter++;
		if (x < array[position])
			right = position-1;
		
		else
			left = position+1;
		
		position = (left + right)/2;

		counter++;
	}
	
	counter++;
	if (x == array[position])
		printf ("\nTo stoixeio %d bre8hke sthn 8esh %d.\n",x,position+1);
	
	else
		printf("\nTo stoixeio %d den yparxei ston pinaka!\n",x);
}



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);

}