(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

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:
  1. Um vetor ordenado;
  2. Dois índices low (início) e high (fim);
  3. Calcular o meio mid = ⌊(low+high)/2⌋;
  4. Comparar vet[mid] com o valor procurado e ajustar low ou high;
  5. 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:
  1. mid = ⌊(low + high) / 2⌋
  2. Se vet[mid] == procurado → achou, retorna mid;
  3. Se vet[mid] < procurado → então o valor só pode estar na metade direita, faz low = mid + 1;
  4. Se vet[mid] > procurado → procura na metade esquerda, faz high = mid – 1.
  5. 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.

Exercícios relacionados