/*
 *  Preenche um vetor ordenado com números aleatórios entre 0 e
 *  ESPALHAMENTO + 1.  Faz várias buscas e exibe a média dos
 *  custos para todas as buscas e para as buscas bem sucedidas.
 */

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

#define ESPALHAMENTO 7
#define TAMANHO 1000

int main () {
  
  int vetor[TAMANHO];
  int valor;
  int i, b, n;
  int encontrado;
  int media, media_sucesso, n_sucesso;
  int direita, esquerda, meio, passo;

  vetor[0] = rand() % ESPALHAMENTO;
  for (i = 1; i < TAMANHO; i++)
    vetor[i] = vetor[i-1] + rand() % ESPALHAMENTO + 1;

  printf("Número de buscas: ");
  scanf("%d", &n);

  media = 0;
  media_sucesso = 0;
  n_sucesso = 0;

  for (b = 0; b < n; b++) {
    encontrado = 0; /*Falso*/
    valor = rand() % (vetor[TAMANHO-1]+1);

    esquerda = 0;
    direita = TAMANHO - 1;
    passo = 0;
    
    while (esquerda <= direita && !encontrado) {
      meio = (direita + esquerda) / 2;
      passo++;
      if (vetor[meio] == valor)
	encontrado = 1; /*Verdadeiro*/
      else if (valor < vetor[meio])
	direita = meio - 1;
      else 
	esquerda = meio + 1;
    }
    
    media += passo;
    if (encontrado) {
      printf ("Valor %d encontrado na posicao %d no passo %d\n", 
               vetor[meio], meio, passo);
      media_sucesso += passo;
      n_sucesso++;
    } else {
      printf ("Valor %d não encontrado\n", valor);
    }
  
  }
  
  printf("Média do custo das buscas: %d\n", media/n);
  printf("Média do custo das buscas com sucesso: %d\n", media_sucesso/n_sucesso);
  
  system("pause");  
  return 0;
}