Busca Linear
Desenvolva um programa no qual seja definido um vetor de números com quaisquer valores (pode haver valores repetidos ou não). O usuário deve ser questionado para digitar um número e em seguida o programa deve indicar se o valor digitado pelo usuário é um elemento presente no vetor ou se não é um elemento presente no vetor.
Desenvolva um programa no qual seja definido um vetor de números com quaisquer valores (pode haver valores repetidos ou não). O usuário deve ser questionado para digitar um número e em seguida o programa deve indicar se o valor digitado pelo usuário é um elemento presente no vetor ou se não é um elemento presente no vetor.
Passo 1
O enunciado pede que você crie um programa que faça o seguinte: (1) defina um vetor com quaisquer valores (pode haver valores repetidos); (2) peça ao usuário para digitar um número; (3) indique se o número digitado é um elemento presente no vetor ou não.
Informações dadas e requisitos importantes:
Informações dadas e requisitos importantes:
- O vetor deve já estar definido no programa (não precisa ser lido do teclado). Vou chamar esse vetor de
. - O usuário fornece um valor (vou chamar de
). - A saída deve ser uma mensagem dizendo se
pertence a ou não. - Podem existir valores repetidos em
. - O enunciado não especifica linguagem ou tratamento de tipos (inteiros/float), então o programa deve tratar casos comuns e ser robusto.
Passo 2
Qual método usar? O enunciado não exige um método específico, então escolhemos o método mais simples e direto: busca linear. Aqui explico por que:
- A busca linear percorre
elemento a elemento comparando cada valor com . - É simples de implementar sem pré-condições (não precisa do vetor ordenado).
- É eficiente o bastante para vetores de tamanho típico em exercícios de prova.
Portanto usaremos a busca linear (também chamada de busca sequencial).
Passo 3
Como funciona a busca linear (explicação didática, passo a passo):
- Começamos no primeiro elemento de
, que tem índice . - Comparamos esse elemento com
. Se forem iguais, paramos e dizemos “encontrado”. - Se não forem iguais, passamos para o próximo elemento (índice
) e repetimos. - Continuamos até terminar os elementos de
. Se chegarmos ao fim sem encontrar igualdade, então não está em .
Exemplo concreto: see , percorremos: comparar com (não), comparar com (sim) → achamos . Se , percorremos todos e não encontramos → não está no vetor.
Passo 4
Pseudocódigo simples da busca linear (para você entender o passo-a-passo de execução):
Aqui
é o número de elementos do vetor
. A ideia chave é «verificar um por um» até achar ou terminar.
Passo 5
Complexidade e observações rápidas para a prova:
- No pior caso, a busca linear verifica todos os elementos, então o tempo é
, onde . - No melhor caso (quando
é o primeiro elemento) o tempo é . - A busca linear não exige que
esteja ordenado. Se o vetor estivesse ordenado e você precisasse de buscas repetidas, poderia usar busca binária com custo , mas a busca binária exige ordenação prévia.
Passo 6
Casos práticos e cuidado com tipos (coisa que normalmente pega na prova):
- Se
contém inteiros e o usuário digita uma string, faça conversão adequada. Uma abordagem comum: tentar converter a entrada para inteiro; se falhar, tentar converter para float; se ainda falhar, tratar como string. - Se houver floats, comparar com igualdade direta pode ser arriscado por precisão (por exemplo,
pode não dar exatamente ). Para floats, use uma tolerância: dois valores e são iguais se , com por exemplo. - Vetor vazio: se
, a busca retorna “não encontrado”. - Duplicatas: se
tem várias ocorrências do mesmo valor, a busca linear retorna “encontrado” na primeira ocorrência — isso já satisfaz o enunciado.
Passo 7
Implementação passo a passo (aqui eu explico cada parte do programa em Python, linha a linha, para você conseguir reproduzir na prova ou adaptar):
- Defina
com alguns valores (você pode escolher quaisquer números). Por exemplo: . - Leia a entrada do usuário como string e tente convertê-la para inteiro ou float (para facilitar comparações numéricas).
- Escreva uma função auxiliar para comparar valores que trate floats com tolerância.
- Escreva a função de busca linear que percorre
e usa a função de comparação. - Ao final, imprima uma mensagem clara indicando se o valor está presente ou não.
Pequena explicação das funções que vamos usar no código:
- parse_input(s): tenta transformar a string
em int ou float; se não conseguir, retorna a string (caso raro). - equal(a,b): compara
e ; se qualquer um for float, usa tolerância ; caso contrário usa igualdade direta. - linear_search(V,x): percorre
e retorna True se encontrar , senão False.
Passo 8
Exemplos de execução (para você visualizar o comportamento):
- Com
e entrada do usuário → saída: “O valor está presente no vetor.” (encontrado). - Com o mesmo
e → saída: “O valor NÃO está presente no vetor.” (não encontrado). - Se o usuário digitar
(float) e houver (inteiro) em , a função de comparação trata isso corretamente convertendo e comparando numericamente (dependendo de como você implementar a conversão).
Passo 9
Dicas para a prova (resumindo e encorajando):
- Memorize a ideia da busca linear: “verifica um por um”. É simples e muito frequentemente pedida.
- Lembre-se da complexidade
. - Se tiver tempo e o vetor estiver ordenado, pense em busca binária; caso contrário, busca linear é a escolha segura.
- Não tenha medo: siga os passos de conversão de entrada e verificação — isso resolve a maior parte dos casos.
Resposta
# Programa de Busca Linear (Python)
# Vetor definido com quaisquer valores (pode ter repetidos)
numbers = [3, 5, 2, 7, 5, 10]
def parse_input(s):
s = s.strip()
# Tenta inteiro primeiro
try:
return int(s)
except ValueError:
pass
# Tenta float
try:
return float(s)
except ValueError:
pass
# Se não for número, retorna string
return s
def equal(a, b, eps=1e-9):
# Compara considerando floats com tolerância
try:
if isinstance(a, float) or isinstance(b, float):
return abs(float(a) - float(b)) < eps
else:
return a == b
except Exception:
# Se não for possível converter, compara como igualdade direta
return a == b
def linear_search(arr, target):
for idx, val in enumerate(arr):
if equal(val, target):
return True
return False
# Leitura do usuário
user_input = input("Digite um número: ")
target = parse_input(user_input)
# Busca
found = linear_search(numbers, target)
# Resultado
if found:
print("O valor está presente no vetor.")
else:
print("O valor NÃO está presente no vetor.")