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. O funcionamento do programa deve seguir a seguinte rotina:
Execução 1:
Digite a quantidade de elementos no vetor: 5
Digite os elementos do vetor: 12345
Digite o elemento procurado: 3
Posição do elemento procurado: 3
Execução 2:
Digite a quantidade de elementos no vetor: 5
Digite os elementos do vetor: 12789
Digite o elemento procurado: 3
Posição do elemento procurado: -1
Digite os elementos do vetor: 12345
Digite o elemento procurado: 3
Posição do elemento procurado: 3
Digite os elementos do vetor: 12789
Digite o elemento procurado: 3
Posição do elemento procurado: -1
Passo 1
O enunciado pede um programa que leia um vetor de inteiros já ordenado, leia um valor alvo e use o método de busca binária para encontrar a posição desse valor no vetor. Se o valor existir, deve imprimir sua posição (contagem iniciada em
); caso contrário, imprimir -
.
Passo 2
A busca binária funciona dividindo repetidamente o espaço de busca ao meio. Dados índices iniciais
e
, calculamos o meio
Se
, encontramos o elemento. Se
, descartamos a metade esquerda fazendo
. Caso contrário, descartamos a metade direita fazendo
. Repetimos enquanto
.
Passo 3
Antes de aplicar a busca, o programa deve:
. Ler o inteiro
, quantidade de elementos.
. Ler os
elementos do vetor (assumimos ordenados em ordem crescente).
. Ler o inteiro alvo
.
Passo 4
Implementamos uma função -indexada ou
:
\(busca_binaria\)(v, n, x)
que retorna a posição
- Inicializar
e . - Enquanto
: - Calcular
. - Se
, retornar . - Se
, fazer . - Senão, fazer
.
- Calcular
- Se sair do laço sem encontrar, retornar
.
Passo 5
No
main
, chamar essa função e imprimir exatamente no formato:Digite a quantidade de elementos no vetor:
Digite os elementos do vetor:
Digite o elemento procurado:
Posição do elemento procurado: X
onde
X
é o resultado obtido.Resposta
#include <stdio.h>
int busca_binaria(int v[], int n, int x) {
int l = 0, r = n - 1;
while (l <= r) {
int m = (l + r) / 2;
if (v[m] == x)
return m + 1; // converte para índice \(1\)-based
else if (v[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1; // não encontrado
}
int main() {
int n;
printf("Digite a quantidade de elementos no vetor: ");
scanf("%d", &n);
int v[n];
printf("Digite os elementos do vetor: ");
for (int i = 0; i < n; i++) {
scanf("%d", &v[i]);
}
int x;
printf("Digite o elemento procurado: ");
scanf("%d", &x);
int pos = busca_binaria(v, n, x);
printf("Posição do elemento procurado: %d\n", pos);
return 0;
}