/* 

Faça uma função 

int busca (int v[], int n, int x); 

que devolve um índice i de v tal que 
v[i] = x, caso x ocorra no vetor, ou 
-1 caso x não ocorra. 

*/

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

void ordena (int v[], int n) {
  int i, j, aux;
  for (i = 0; i < n - 1; i ++)
    for (j = 0; j < n - i - 1; j++)
      if (v[j] > v[j+1]){
	aux = v[j];
	v[j] = v[j+1];
	v[j+1] = aux;
      }
}

int buscaRec (int v[], int n, int x){
  if (n == 0)
    return -1;
  if (v[n-1] == x)
    return n - 1;
  return (buscaRec (v, n - 1, x));
}

/* devolve i se v[i] = x ou -1 se x não ocorre no vetor */
int busca1 (int v[], int n, int x) {
  int i;
  for (i = 0; i < n; i++) /* v[j] != x para todo j = 0,.., i-1 */ 
    if (v[i] == x)
      return i;
  return -1;
}

int busca2 (int v[], int n, int x) {
  int i;
  for (i = n - 1; i >= 0 && v[i] != x; i--);
  return i;
}


/* E se o vetor estiver ordenado? */

/* estamos procurando x num pedaço do vetor v[ini..fim] e está ordenado 
   em ordem crescente */ 
int buscaBinRec (int v[], int ini, int fim, int x) {
  int meio; 
  if (ini > fim)
    return -1;
  meio = (ini + fim)/2;
  if (v[meio] == x)
    return meio;
  if (v[meio] < x)
    return buscaBinRec (v, meio + 1, fim, x);
  return buscaBinRec (v, ini, meio - 1, x);
}
      






int main() {
  int n, *v, i, x;
  printf("Digite n: ");
  scanf("%d", &n);
  v = malloc (n * sizeof(int));
  for (i = 0; i < n; i++)
    v[i] = rand() % 1000;
  ordena (v, n);
  for (i = 0; i < n; i++) printf("%d ", v[i]);
  
  printf("\n");
  printf("Digite x: ");
  scanf("%d", &x);
  i = buscaBinRec (v, 0, n-1, x);
  if (i >= 0)
    printf("%d ocorre na posição %d (%d)\n", x, i, v[i]);
  else
    printf("%d não ocorre no vetor\n", x);
  free (v); 
  return 0;
}