#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <string.h>

#define MAX 100

// Declarações //



typedef struct reg {
		int chave;
		char nome[50];
} registro;

typedef struct s_ind {
		int chave,endereco;
} index;

registro lista[MAX];
index indice[MAX];

// Lista de nomes - 24 nomes //

char *nomes[]= {"Marcelo","Joao","Larissa","Pedro","Ricardo","Leandro","Luiz","Manuel","Maria","Roberta","Renata",
"Raimunda","Nelsa","Gustavo","Bruno","Sofia","Kelly","Anderson","John","Roberto","Gabriela","Giovana","Raissa",
"Murilo","Dojival"}; 

// Lista de Sobrenomes - 8 Sobrenomes //

char *sobrenomes[] = {"Valdo","Silva","Rodrigues","Silveira","DeBastos","Lima","Pinha","Santos","Muniz",
"Nack","Neckel" }; // 11 Sobrenomes

void popular();
void ler();
void mostra();
int partition( index *a, int l, int r);
void quickSort( index *a, int l, int r);
int binsrch(index *pos,int tmp_mat,int low, int high);
FILE *arquivo;


// Fim declarações

main() {
       int posicao,arqp,i;
       char nome[50];
       popular();
       ler();
       quickSort(indice,0,MAX-1);
       printf("Digite a chave a ser pesquisada: ");
       scanf("%d",&i);
       posicao = binsrch(indice,i,0,MAX-1);
       if(posicao > 0) {
           printf("Posição no array organizado: %d\n",posicao);
           arqp = indice[posicao].endereco;
           if((arquivo=fopen("registro.txt","r"))==NULL) printf("erro no arquivo");
           fseek(arquivo,arqp,0);
           fscanf(arquivo,"%d %s",&arqp,nome);
           printf("Chave: %d --- Nome: %s",arqp,nome);
           
       }
       else printf("Não encontrou !");
       getche();
       
       
       }

void popular() {
     //Declarações
     srand(time(NULL)); // Randomizando
     int i;
     //Fim declarações
     if((arquivo=fopen("registro.txt","w"))==NULL) printf("erro no arquivo");
     for(i=0;i<MAX;i++) {
        lista[i].chave = rand() % 100000;
        sprintf(lista[i].nome,"%s+%s",nomes[rand() % 24],sobrenomes[rand() % 11]);
        fprintf(arquivo,"%d %s\n",lista[i].chave,lista[i].nome);     
     }
     fclose(arquivo);
     
}

void mostra() {
     //Declaraçoes
     int i;
     //Fim declarações
     for(i=0;i<MAX;i++) {
        printf("Chave: %d --- Endereço: %d\n",indice[i].chave,indice[i].endereco);
     }
     
     
     }
     
void ler() {
     //Declarações//
     int i,j;
     char temp[40];
     //Fim declarações
     //rewind(arquivo);
     if((arquivo=fopen("registro.txt","r"))==NULL) printf("erro no arquivo");
     fscanf(arquivo,"%d %s",&indice[0].chave,temp);
     for(i=0;i<MAX;i++) {
        indice[i].endereco = ftell(arquivo);
        fscanf(arquivo,"%d %s",&indice[i].chave,temp);
     }
     fclose(arquivo);
     
}

int partition(index *a, int l, int r) {
   int pivot, i, j, t;
   pivot = a[l].chave;
   i = l; j = r+1;
		
   while( 1)
   {
   	do ++i; while( a[i].chave <= pivot && i <= r );
   	do --j; while( a[j].chave > pivot );
   	if( i >= j ) break;
   	t = a[i].chave; a[i].chave = a[j].chave; a[j].chave = t;
   }
   t = a[l].chave; a[l].chave = a[j].chave; a[j].chave = t;
   return j;
}

void quickSort( index *a, int l, int r)
{
   int j;

   if( l < r ) 
   {
   	// divide and conquer
        j = partition( a, l, r);
       quickSort( a, l, j-1);
       quickSort( a, j+1, r);
   }
	
}

int binsrch(index *pos,int tmp_mat,int low, int high)
{
    int meio;
    if(low>high)
       return(-1);
    meio=(high+low)/2;
    if(tmp_mat==pos[meio].chave)
       return (meio);
    if(tmp_mat<pos[meio].chave)
      return(binsrch(pos,tmp_mat,low,meio-1));
    return(binsrch(pos,tmp_mat,meio+1,high));
    
    
}