/* *************************************************************
 * IMPORTANTE: Vejam o uso de funçoes cujos parâmetros sao vetores 
 * (variáveis indexadas simples).
 * Notem como é feita a declaracao dos prototipos de tais funcoes.
 * Notem como é feita a chamada de tais funçoes.
 */

/*
 * arquivo: busca_binaria.c
 * ------------------------
 * Este programa recebe uma sequencia crescente de n inteiros
 * (n <= 100) e um inteiro x.  Determina se x ocorre na sequencia
 * dada.
 */


#include <stdio.h>

#define NMAX 100

/* prototipos das funcoes */

void leia_vetor(int v[], int n);
int busca_binaria(int v[], int n, int x);

/************************************************************/

int main()
{
  int n, t;
  int s[NMAX], x;

  printf("Forneca o valor de n: ");
  scanf("%d", &n);

  leia_vetor(s, n);

  printf("Forneca o elemento x procurado: ");
  scanf("%d", &x);


  t = busca_binaria(s, n, x);
  if (t >= 0)
    printf("Temos s[%d] = %d.\n", t, x);
  else
    printf("O elemento %d nao ocorre na sequencia.\n", x);

  return 0;
}

/*----------------------------------------------------------*/
/*
 * leia_vetor():
 * =============
 * Recebe um vetor de int v[] e um inteiro n.
 * Le n reais e os coloca em em v[], isto e', em
 * v[0],...,v[n-1].
 */
void leia_vetor(int v[], int n)
{
  int i;

  printf("Forneca os %d inteiros: ", n);
  for (i = 0; i < n; i++)
    scanf("%d", &v[i]);
}

/*-----------------------------------------------------------*/
/*
 * busca_binaria():
 * ================
 * Recebe um vetor crescente de n int v[0..n-1], um inteiro n, 
 * e um inteiro z; devolve i se v[i] = z.  Devolve -1
 * caso z nao ocorra em v[].
 */

int busca_binaria(int v[], int n, int x)
{
  int esq = 0, dir = n - 1, m;

  while (dir >= esq) {
    m = (esq + dir) / 2;
    if (x == v[m])
      return m;
    if (x < v[m])
      dir = m - 1;
    else
      esq = m + 1;
  }
  return -1;
}