Exercícios sobre busca binária

Exercícios sobre busca binária

por José Coelho de Pina -
Número de respostas: 5

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 olho roxo.
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.
Em resposta à José Coelho de Pina

Re: Exercícios sobre busca binária

por Gustavo Estrela de Matos -

O que eu acredito que esteja errado é o valor "m" que a função retorna. Quando você chama recursivamente essa função ela vai mudando o seu tamanho "n", e como "m" depende de "n", o valor de "m" de quando for encontrado x vai ser um "m" do vetor local da função, e não do vetor v que estamos usando.
Exemplo, se quando você acha x, o vetor tem tamanho n = 1, o valor retornado será m = 0. 

Em resposta à José Coelho de Pina

Re: Exercícios sobre busca binária

por Gustavo Estrela de Matos -

Também, no ultimo return, acho que deveria ser return "return buscaBinaria(x, m, v);"
Vou dar um exemplo:
n = 8
v[8] = {0,1,2,3,4,5,6,7};
se x é 3:
Na primeira chamada da função buscaBinaria temos os valores acima e m = 4;
Se chamarmos a função buscaBinaria novamente com n = 3 (m-1) teriamos o vetor v={0,1,2}, sendo que o certo seria v = {0,1,2,3}.

 

Em resposta à Gustavo Estrela de Matos

Re: Exercícios sobre busca binária

por José Coelho de Pina -

Também, no ultimo return, acho que deveria ser return "return buscaBinaria(x, m, v);"

Verdade.
O segundo parâmetro é o número de elementos  no vetor e não o índice do último elemento.

Pessoal, como seria uma versão correta dessa função?

Em resposta à José Coelho de Pina

Re: Exercícios sobre busca binária

por Gustavo Estrela de Matos -

Fiz uma versão que dá certo exceto quando o valor não está presente no vetor triste

int
buscaBinaria (int x, int n, int *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])+(m+1);
return buscaBinaria(x, m, v);
}
Eu até sei qual é o problema:
Quando eu retorno -1, as outras chamadas continuam somando (m+1) no return
__________________________________________________________________________

EDIT: agora funciona

int
buscaBinaria (int x, int n, int *v)
{
int m;
int a;
if (n == 0) return -1;
m = n/2;
if (v[m] == x) return m;
if (v[m] < x)
{
a = buscaBinaria(x,n-m-1, &v[m+1]);
return a + (m+1)*(a!=-1);
}
return buscaBinaria(x, m, v);
}