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.

P.S. No tópico "Dúvidas e erros no EP2" coloquei uma pergunta que continua sem resposta triste.

Em resposta à José Coelho de Pina

Re: Exercícios sobre busca binária

por Frederico Lage Ferreira -

O problema é que a cada recursão, ao passar um endereço diferente do início do vetor a ser examinado, a posição relativa muda. No final o valor do índice m devolvido não será válido para o vetor original.

Exemplo: Tendo um vetor de 10 posições (10, 20, 30, 40, 50 , 60, 70, 80, 90, 100) com o valor procurado (x = 100) estando na última casa:

- Na primeira chamada da função, n = 10, m = 5. Logo, v[5] < x , chama função buscaBinaria(100, 4, &v[6]).

- Nessa primeira recursão, n = 4, m = 2 e o vetor v tem a sua posição inicial apontando para aquele que era o sétimo valor no vetor original. Assim v[2] = 90 < x, chama novamente buscaBinaria(100, 1, &v[3]).

- Na segunda recursão, n = 1, m = 0 e o vetor v tem a sua posição inicial apontando para aquele que era o décimo valor no vetor original. Assim v[0] = 100 e ele devolve m = 0.

Assim, o valor retornado não corresponde ao índice correto no vetor original. Para corrigir, basta fazer isso:

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 m + 1 + buscaBinaria(x,n-m-1,&v[m+1]);

return buscaBinaria(x,m-1,v);

}

 

Basta colocar a correção no caso v[m] < x, pois no outro caso a posição inicial do vetor não muda.

Em resposta à Frederico Lage Ferreira

Re: Exercícios sobre busca binária

por José Coelho de Pina -

Oi Frederico,

O problema é que a cada recursão, ao passar um endereço diferente do início do vetor a ser examinado, a posição relativa muda. No final o valor do índice m devolvido não será válido para o vetor original.

BINGO! É isso ai!

Assim, o valor retornado não corresponde ao índice correto no vetor original.
[. . .]

A sua solução ficou muito boa!
Agora, qual o valor que a função retorna se o elemento procurado não estiver no vetor?

Em resposta à José Coelho de Pina

Re: Exercícios sobre busca binária

por Frederico Lage Ferreira -

Hmmm... tinha me esquecido desse detalhe... dessa maneira, quando não for encontrado ele pode acabar somando m+1-1 e devolvendo um índice incorreto.

Aliás, percebi um outro problema também.

A chamada buscaBinaria(x,m-1,v) usa um valor de n menor do que a quantidade real de elementos na primeira metade (pegando o meu exemplo anterior novamente, se o elemento procurado fosse 50, ele não seria encontrado porque ao final da primeira execução seria chamado buscaBinaria(50,4,v) que só examinaria o vetor da posição 0 até 3 ). Sem falar que ela poderia acabar chamando um n = -1 se o valor procurado fosse menor que o primeiro.

Para tentar solucionar as duas coisas


int buscaBinaria (int x, int n, inv *v) {

int m;

int i = 0;

if (n == 0) return -1;

m = n/2;

if (v[m] == x) return m;

if (v[m] < x)

{

    i = buscaBinaria(x,n-m-1,&v[m+1]);

    if ( i == -1) return -1; 

    return m + 1 + i;

}

return buscaBinaria(x,m,v);

}

Em resposta à Frederico Lage Ferreira

Re: Exercícios sobre busca binária

por José Coelho de Pina -

A chamada buscaBinaria(x,m-1,v) usa um valor de n menor do que a quantidade real de elementos na primeira metade

De fato, o segundo argumento é o número de elementos do vetor e não o índice do último elemento.

Para tentar solucionar as duas coisas
[. . .]

Beleza!

Em resposta à José Coelho de Pina

Re: Exercícios sobre busca binária

por José Coelho de Pina -

Aqui vão mais alguns exercícios sobre pilhas.

Vocês podem encontrar vários exercícios na página Pilhas de Paulo Feofiloff.
Sugiro que vocês façam pelo menos o 1, 3 (sobre sequências de parenteses e colchetes bem-formadas), 6, 7 e 12.