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
iteração: 3 elementos descartados
iteração: 1 elemento descartado
Digite os elementos do vetor: 12345
Digite o elemento procurado: 1
Posição do elemento procurado: 1
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.
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
):
buscaBinariaComDescartes
:
Passo 3
Explicação do cálculo de descartes:
- Antes de atualizar
e , o vetor atual tem elementos. - Após escolher a metade que permanece na busca, o novo intervalo tem
. - Logo, o número de elementos retirados é
Passo 4
Aplicando ao exemplo dado:
- Dados:
, , .
Iteração
:
,
,
imprime “ ª iteração:
elementos descartados”
,
imprime “
Iteração
:
,
,
encontrou, retorna posição
encontrou, retorna posição
Resposta
Posição do elemento procurado:
ª iteração:
elementos descartados
ª iteração:
elemento descartado