Altere o método de busca binária do exercício 1 para que, a cada divisão do vetor, ele imprima quantos elementos foram descartados na busca.
Digite a quantidade de elementos no vetor: 5
Digite os elementos do vetor: 12345
Digite o elemento procurado: 1
Posição do elemento procurado: 1
1^ a iteração: 3 elementos descartados
2^a iteração: 1 elemento descartado

Passo 1

O enunciado pede para modificar o método de busca binária clássico de modo que, a cada iteração (divisão do vetor), o algoritmo imprima quantos elementos foram descartados da busca.
Conteúdo: busca binária em vetor ordenado e contagem de elementos eliminados em cada divisão.

Passo 2

Esboço do algoritmo modificado em pseudocódigo (índices iniciam em 1):
buscaBinariaComDescartes A[1n], chave:
inicio 1
fim n
iter 1
enquanto inicio <= fim façaç
tamanhoAntes fim - inicio + 1
meio lfloor inicio + fim2 rfloor
se A[meio] = chave entãoã
novoInicio meio
novoFim meio
senão se A[meio] < chave entãoãã
novoInicio meio + 1
novoFim fim
senãoã
novoInicio inicio
novoFim meio - 1
fim se
tamanhoDepois novoFim - novoInicio + 1
descartados tamanhoAntes - tamanhoDepois
imprimir iter^a iteração: descartados e<=mentos descartadosçã
iter iter + 1
inicio novoInicio
fim novoFim
se A[meio] = chave entãoã
retorne meio
fim se
fim enquanto
retorne -1 // não encontradoã

Passo 3

Explicação do cálculo de descartes:
  • Antes de atualizar inicio e fim, o vetor atual tem tamanhoAntes = fim - inicio + 1 elementos.
  • Após escolher a metade que permanece na busca, o novo intervalo tem tamanhoDepois = novoFim - novoInicio + 1.
  • Logo, o número de elementos retirados é
descartados = tamanhoAntes - tamanhoDepois

Passo 4

Aplicando ao exemplo dado:
  • Dados: n=5, A=[1,2,3,4,5], chave=1.
Iteração 1:
inicio=1, fim=5 Rightarrow tamanhoAntes=5
meio = lfloor 1+52 rfloor = 3, A[3]=3 > 1 Rightarrow nova faixa = [12] Rightarrow tamanhoDepois = 2
descartados = 5 - 2 = 3
imprime “ 1ª iteração: 3 elementos descartados”
novo inicio = 1, novo fim = 2
Iteração 2:
inicio = 1, fim = 2 Rightarrow tamanhoAntes = 2
meio = lfloor 1+22 rfloor = 1, A[1] = 1 Rightarrow nova faixa = [11] Rightarrow tamanhoDepois = 1
descartados = 2 - 1 = 1
encontrou, retorna posição 1

Resposta

Posição do elemento procurado: 11ª iteração: 3 elementos descartados
2ª iteração: 1 elemento descartado

Exercícios relacionados