// [19/11/2004]
// MAC110 - 2004
//
// Exemplo: vetor + apontadores
// 
// Vetor: é implementado através de cálculo de endereço inicial + deslocamento,
//        logo através de "apontador + deslocamento", ou seja, a variável inteira
// "v[10+i]" é pega fazendo a conta "posição inicial de v + (núm. bytes int)*(10+i)"

// Função para testar se vetor "vet", com N elementos, está ordenado
// retorna: 0, se não estiver ordenado
//          1, se estiver ordenado
int testaOrdem (int vet [], int N) {
  int i;
  for (i=0; i<N-1; i++)
      if (vet[i]>vet[i+1]) return 0;
  return 1;
  }

// Função que busca um elemento x num vetor vet ordenado crescente
// retorna: -1, se x não está no vetor
//           i, se x está na posição i (entre 0 e N-1)
int buscaBinaria (int x, int vet [], int N) {
  int i, // início da busca
      f, // fim da busca
      m; // "ponto médio"

  if (!testaOrdem(vet,N)) return -1; // erro, desordenado
  i=0; f=N-1;
  while (i<=f) {
    m = (i+f)/2;
    if (x==vet[m]) return m; // encontrou elemento, retorne
    if (x>vet[m]) // ignore parte "esquerda"
       i = m+1;
    else
    // if (x<vet[m]) // ignore parte "direita"
       f = m-1;
    }
  return -1; // não achou
  }


int main (void) {
  int v [] =  { -2, -1, 3, 5, 5, 6, 7, 9, 10, 12}, // define o vetor de elementos
      N    = 10,
      iResp,
      vResp,
      x    =  1;

  // busca o elemento 1 (que não está no vetor)
  printf("Busca elemento %d: posição %d\n", x, buscaBinaria(x, v, N));

  // busca o elemento 1 (que não está no vetor)
  x = 1;
  iResp = buscaBinaria(x, v, N);   // esta "versão" é para listar o conteúdo
  if (iResp!=-1) vResp = v[iResp]; // encontrado, que será "v[iResp]", mas
  else vResp = -111111;            // se x não está, "responda" -111111
  printf("Busca elemento %d: vet[%d] = %d\n", x, iResp, vResp);

  // busca o elemento 3 (que está no vetor)
  x = 3;
  iResp = buscaBinaria(x, v, N);
  if (iResp!=-1) vResp = v[iResp];
  else vResp = -111111;
  printf("Busca elemento %d: vet[%d] = %d\n", x, iResp, vResp);

  // busca o elemento 5 (que está no vetor)
  x = 5;
  iResp = buscaBinaria(x, v, N);
  if (iResp!=-1) vResp = v[iResp];
  else vResp = -111111;
  printf("Busca elemento %d: vet[%d] = %d\n", x, iResp, vResp);
	 
  }