/*
 *  Preenche um vetor com números aleatórios entre 0 e TAMANHO-1,
 *  garantindo que cada número aparece apenas uma vez no vetor.
 *  Faz várias buscas e exibe a média dos custos para todas as
 *  buscas.
 */

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

#define TAMANHO 1000

int main () {
  
  int vetor[TAMANHO];
  int valor;
  int i, j, b, n, aux;
  int encontrado;
  int media;
  
  //Preenche vetor com os valores de i
  for (i = 0; i < TAMANHO; i++)
    vetor[i] = i;
  
  //Embaralha os elementos do vetor
  for (i = 0; i < TAMANHO; i++) {
    j = rand() % TAMANHO;
    aux = vetor[i];
    vetor[i] = vetor[j];
    vetor[j] = aux;
  }
  
  printf("Número de buscas: ");
  scanf("%d", &n);

  media = 0;

  for (b = 0; b < n; b++) {
    i = 0;
    encontrado = 0; /*Falso*/
    valor = rand() % TAMANHO;
    
    while (i < TAMANHO && !encontrado) {
      if (vetor[i] == valor) {
	encontrado = 1; /*Verdadeiro*/
      } else {
	i++;
      }
    }
    media += i;
    
    if (encontrado) {
      printf ("Valor %d encontrado na posicao %d\n", vetor[i], i);
    } else {
      printf ("Valor %d não encontrado\n", valor);
    }
  }

  printf("Média do custo das buscas: %d\n", media/n);
  
  system("pause");  
  return 0;
}