-----------------------------------------------------------------------------
 MAC-110 - Variáveis indexadas e uso de funções cujos parâmetros são vetores 
=============================================================================
      Busca Binária: algoritmo eficiente para busca em vetor ordenado


/*
 * 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


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

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

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

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

  leia_vetor(seq, n);

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


  t = busca_binaria(seq, n, x);
  if (t >= 0)
    printf("Temos seq[%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 inteiros 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 inteiros 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, dir, meio;
  esq = 0;
  dir = n - 1; 

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