/* 
    Programa de prueba del algoritmo de Búsqueda Dicotómica
*/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>



#define maxTalla    100000

typedef double tipo;

void InVec(tipo *V)
{
    int i;
    for (i=1; i<=maxTalla; i++)
	V[i]=i;
	
}


int Binaria(tipo *V, tipo xx,  int talla)
{
    int i, j, cent, res;
    
    i=1;
    j=talla;
    res=0;
    
    do
    {
	cent=(i+j)/2;
	if (V[cent]==xx)
	{
	    i=j+1;
	    res=cent;
	}
	else
	{
	    if (xx<V[cent])
		j=cent-1;
	    else
		i=cent+1;
	}
	
    }
    while (i<=j);
    return(res);
}


float CalculaMedia(tipo *V, int talla)
{
    int pos, xx, i, nbusq=100, rep=10000, m;
    float t0, t1, t2, tt;
    
    tt=0.0;
    t0=clock();
    for (i=0;i<nbusq;i++)
    {
	xx=V[rand() % talla];
	t1=clock()/(float)CLOCKS_PER_SEC;
	for (m=0;m<rep;m++)
	    pos=Binaria(V, xx, talla);
	t2=clock()/(float)CLOCKS_PER_SEC;
	tt=tt+(float)(t2-t1);
    }
    return(tt/(float)(rep*nbusq));
}


void main(void)
{
    int talla;
    float tiempo;
    tipo vtipo[maxTalla+1];
    FILE *fich;
    
    if (!(fich=fopen("salida.dat", "w")))
    {
	printf("ERROR ABRIENDO FICHERO \n");
	exit(1);
    }
    InVec(vtipo);
    talla=100;
    do
    {
	printf("TALLA:  %d\n", talla);
	tiempo=CalculaMedia(vtipo, talla);
	fprintf(fich, "%d\t%5.10f\n", talla, tiempo);
	talla=talla+100;
    }
    while(talla<=2000);
    fclose(fich);
}



/***********************
 * 
 *	COMPILACION
 * 
 *	gcc -O0 -o nombre nombre.c -lm
 ************************/