(2) Faça um programa que use o método de busca binária para encontrar e imprimir a posição de um determinado elemento no vetor. Se o elemento não existir, seu programa deve imprimir o valor -1 .
Considere um vetor de tamanho 5
Não se esqueçam que o vetor deve estar ordenado
Digite os elementos do vetor: 12345
Digite o elemento procurado: 3
Posição do elemento procurado: 2
Digite os elementos do vetor: 4871128
Digite o elemento procurado: 3
Posição do elemento procurado: -1
Não se esqueçam que o vetor deve estar ordenado
Digite o elemento procurado: 3
Posição do elemento procurado: 2
Digite o elemento procurado: 3
Posição do elemento procurado: -1
Passo 1
Beleza, temos que fazer um programa de “busca binária” num vetor já ordenado de tamanho 5. A ideia é: dado um vetor e um valor “procurado”, a gente encontra a posição desse valor (índice) se ele existir, ou retorna –1 se não.
Conteúdo: busca binária (divide pra conquistar).
O que precisamos:
Conteúdo: busca binária (divide pra conquistar).
O que precisamos:
- Um vetor ordenado;
- Dois índices
low
(início) ehigh
(fim); - Calcular o meio
mid = ⌊(low+high)/2⌋
; - Comparar
vet[mid]
com o valor procurado e ajustarlow
ouhigh
; - Repetir até achar ou esgotar o intervalo.
Passo 2
Primeiro, a gente lê o vetor de 5 elementos e o valor que quer achar. Exemplo 1: vetor = [1,2,3,4,5], procurado = 3.
Passo 3
Inicializa:
low = 0
high = n–1 // n = 5, então high = 4
Passo 4
Enquanto
low ≤ high
, faz:- mid = ⌊(low + high) / 2⌋
- Se vet[mid] == procurado → achou, retorna mid;
- Se vet[mid] < procurado → então o valor só pode estar na metade direita, faz low = mid + 1;
- Se vet[mid] > procurado → procura na metade esquerda, faz high = mid – 1.
- Volta pro passo 1 até low > high.
Passo 5
Se sair do laço sem achar (low > high), significa que o elemento não existe no vetor. Aí retornamos –1.
Resposta
Para o exemplo “12345” e procurado 3 → posição 2.
Para o exemplo “4871128” e procurado 3 → posição –1.
Para o exemplo “4871128” e procurado 3 → posição –1.