Salve,
Vocês podem encontrar vários exercícios na página Busca em vetor ordenado.
Sugiro que vocês façam pelo menos o 3 e 6 para ver se entenderam a função buscaBinaria.
O exercício 14 também é divertido e tem que ter uma sacada.
Outro exercício é o seguinte.
No final da aula de hoje escrevi (ou rascunhei) uma função busca binária recursiva que tem um problema .
Qual é o problema? Como consertar? A função está logo a seguir:
/* A função abaixo recebe um número x e um vetor * crescente v[0..n-1]. Ela devolve um índice m * em 0..n-1 tal que v[m] == x. Se tal m não existe, */ devolve -1. int buscaBinaria (int x, int n, inv *v) { int m; if (n == 0) return -1; m = n/2; if (v[m] == x) return m; if (v[m] < x) return buscaBinaria(x,n-m-1,&v[m+1]); return buscaBinaria(x,m-1,v); }
Observações:
- As declarações "int v[]" e "int *v" em protótipos de funções são equivalentes. Escolhemos "int *v" apenas para deixar explícito que ema ambas os casos o que está sendo passado como parâmetro é um endereço(!).
- As expressões "&v[m+1]'' e "v+m+1" são equivalentes (=tem o mesmo valor = representam o mesmo endereço). A segunda expressão utiliza aritmética de ponteiros.