Elabore um programa que preencha um vetor com números inteiros digitados pelo usuário (no máximo 1000 números). Após a digitação, o vetor deverá ser ordenado e, em seguida, pesquisado inúmeras vezes (utilizar um algoritmo de busca em tabelas ordenadas). A cada pesquisa deverá ser retornado a posição (ordem de entrada) do número ou uma mensagem explicativa quando ele não for encontrado. Tanto a entrada quanto a pesquisa serão finalizadas se o usuário digitar -999.
Passo 1
O objetivo é criar um programa que leia até 1000 inteiros (parando se o usuário digitar -999), armazene também a posição de entrada de cada número, ordene esses pares valor–posição e depois permita pesquisas múltiplas usando busca binária, retornando a posição original ou mensagem de “não encontrado”. Vamos precisar entender vetores, structs, funções de ordenação (qsort) e busca binária em vetores ordenados.
Passo 2
Para manter o valor e sua ordem de entrada, definimos uma struct contendo dois campos: o valor lido e a posição em que foi lido (1 a n). Assim conseguimos ordenar apenas pelo valor, mas ainda saber onde estava originalmente.
Passo 3
Usamos a função qsort da biblioteca padrão do C para ordenar o vetor de structs. O qsort requer um comparador que receba dois ponteiros genéricos e retorne um inteiro negativo, zero ou positivo conforme o primeiro valor seja menor, igual ou maior que o segundo.
Passo 4
Implementamos a busca binária numa função que recebe o vetor de structs ordenado, seu tamanho e a chave a buscar. No laço, com índices left e right, calculamos mid = left + (right-left)/2 e comparamos arr[mid].value com a chave, ajustando left ou right até encontrar ou esgotar o intervalo.
Passo 5
No main(), fazemos três etapas: (1) Leitura dos números até -999 preenchendo o vetor de structs; (2) Chamada de qsort para ordenar pelo campo value; (3) Loop de leitura das chaves de busca até -999, chamando a função de busca binária e imprimindo a posição original (ou mensagem de não encontrado).
Resposta
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
// Definimos um tipo para armazenar valor e posição original
typedef struct {
int value;
int pos;
} Item;
typedef struct {
int value;
int pos;
} Item;
// Função de comparação para qsort: ordena por value
int cmpItem(const void *a, const void *b) {
Item *ia = (Item *)a;
Item *ib = (Item *)b;
return ia->value - ib->value;
}
int cmpItem(const void *a, const void *b) {
Item *ia = (Item *)a;
Item *ib = (Item *)b;
return ia->value - ib->value;
}
// Busca binária em vetor de Item, retorna índice no vetor ordenado ou -1 se não achar
int binary_search(Item arr[], int n, int key) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid].value == key) {
return mid;
} else if (arr[mid].value < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int binary_search(Item arr[], int n, int key) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid].value == key) {
return mid;
} else if (arr[mid].value < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
Item arr[1000];
int n = 0;
int x;
Item arr[1000];
int n = 0;
int x;
// Leitura dos números até -999 ou até 1000 elementos
while (n < 1000) {
if (scanf("%d", &x) != 1) return 0;
if (x == -999) break;
arr[n].value = x;
arr[n].pos = n + 1; // posição de entrada (1-based)
n++;
}
// Ordena o vetor pelo campo value
qsort(arr, n, sizeof(Item), cmpItem);
// Loop de pesquisa até digitar -999
while (1) {
if (scanf("%d", &x) != 1) break;
if (x == -999) break;
int idx = binary_search(arr, n, x);
if (idx >= 0) {
printf("%d encontrado na posicao de entrada %d\n", x, arr[idx].pos);
} else {
printf("%d nao encontrado\n", x);
}
}
return 0;
}