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.

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:
  • O vetor deve já estar definido no programa (não precisa ser lido do teclado). Vou chamar esse vetor de V.
  • O usuário fornece um valor (vou chamar de x).
  • A saída deve ser uma mensagem dizendo se x pertence a V ou não.
  • Podem existir valores repetidos em V.
  • 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 V elemento a elemento comparando cada valor com x.
  • É 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):
  1. Começamos no primeiro elemento de V, que tem índice 0.
  2. Comparamos esse elemento com x. Se forem iguais, paramos e dizemos “encontrado”.
  3. Se não forem iguais, passamos para o próximo elemento (índice 1) e repetimos.
  4. Continuamos até terminar os elementos de V. Se chegarmos ao fim sem encontrar igualdade, então x não está em V.
    Exemplo concreto: se V = [3,5,2,7,5] e x = 5, percorremos: comparar com 3 (não), comparar com 5 (sim) → achamos x. Se x = 8, 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):
\text{função } \text{linear\_search}(V, x):\\\ \quad \text{para cada índice } i \text{ de } 0 \text{ até } |V|-1:\\\ \quad\quad \text{se } V[i] = x \text{ então retorne verdadeiro}\\\ \quad \text{retorne falso}çãíéã
Aqui |V| é o número de elementos do vetor V. 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 é O(n), onde n = |V|.
  • No melhor caso (quando x é o primeiro elemento) o tempo é O(1).
  • A busca linear não exige que V esteja ordenado. Se o vetor estivesse ordenado e você precisasse de buscas repetidas, poderia usar busca binária com custo O(\log n), 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 V 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, 0,1+0,2 pode não dar exatamente 0,3). Para floats, use uma tolerância: dois valores a e b são iguais se |a-b| < \varepsilon, com \varepsilon=10^{-9} por exemplo.
  • Vetor vazio: se |V|=0, a busca retorna “não encontrado”.
  • Duplicatas: se V 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 V com alguns valores (você pode escolher quaisquer números). Por exemplo: V = [3, 5, 2, 7, 5, 10].
  • 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 V 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 s em int ou float; se não conseguir, retorna a string (caso raro).
  • equal(a,b): compara a e b; se qualquer um for float, usa tolerância \varepsilon; caso contrário usa igualdade direta.
  • linear_search(V,x): percorre V e retorna True se encontrar x, senão False.

Passo 8

Exemplos de execução (para você visualizar o comportamento):
  • Com V=[3,5,2,7,5] e entrada do usuário x=5 → saída: “O valor está presente no vetor.” (encontrado).
  • Com o mesmo V e x=8 → saída: “O valor NÃO está presente no vetor.” (não encontrado).
  • Se o usuário digitar x=5,0 (float) e houver 5 (inteiro) em V, 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 O(n).
  • 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.")

Exercícios relacionados