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

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 1); caso contrário, imprimir - 1.

Passo 2

A busca binária funciona dividindo repetidamente o espaço de busca ao meio. Dados índices iniciais ell=0 e r=n-1, calculamos o meio
m = llfloor (ell + r)/2 rrfloor
Se v[m] = x, encontramos o elemento. Se v[m] < x, descartamos a metade esquerda fazendo ell = m+1. Caso contrário, descartamos a metade direita fazendo r = m-1. Repetimos enquanto ell <= r.

Passo 3

Antes de aplicar a busca, o programa deve:
1. Ler o inteiro n, quantidade de elementos.
2. Ler os n elementos do vetor (assumimos ordenados em ordem crescente).
3. Ler o inteiro alvo x.

Passo 4

Implementamos uma função \(busca_binaria\)(v, n, x) que retorna a posição -indexada ou :
  • Inicializar e .
  • Enquanto :
    • Calcular .
    • Se , retornar .
    • Se , fazer .
    • Senão, fazer .
  • 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;
}

Exercícios relacionados