Capítulo 14: Algoritmos de Pesquisa e Manipulação em Vetores

🎯 Objetivo da Aula

Armazenar dados em um vetor é apenas a primeira etapa. No dia a dia de uma empresa, a verdadeira utilidade de um banco de dados em memória é a capacidade de pesquisar rapidamente se um item existe, encontrar o maior valor faturado e filtrar registros que atendam a determinadas regras.

Nesta aula, você aprenderá a:

  1. Implementar o algoritmo clássico de Busca Sequencial / Linear (Linear Search).
  2. Utilizar a técnica da Flag Booleana (encontrado <- FALSO) para evitar avisos falsos de “não encontrado”.
  3. Desenvolver o algoritmo de localização do Maior e Menor Elemento com rastreamento de posição.
  4. Aplicar filtros estatísticos sobre vetores preenchidos.

📥 Material de Apoio e Código-Fonte da Aula:

🏢 O Cenário Prático (Seu Desafio)

Situação: O almoxarifado central da FastLog armazena milhares de peças e pneus de reposição para caminhões. Quando um mecânico chega ao balcão solicitando a peça "PN-295-80", o atendente precisa digitar esse código no terminal. O sistema deve varrer todo o catálogo de estoque e responder imediatamente:

  1. Se a peça foi Localizada ou Não Cadastrada.
  2. Em qual Prateleira/Posição do armazém ela está guardada.
  3. Qual o Saldo Disponível em estoque.

Missão: Construir o Buscador de Peças FastLog, aplicando o algoritmo de Busca Linear com controle por flag booleana e localização de maiores saldos.

🧠 Fundamentos: O Algoritmo de Busca Linear

1. O Funcionamento da Busca Linear

A Busca Linear (Linear Search) é o método de pesquisa mais fundamental da computação: ela inspeciona o vetor elemento por elemento, do índice 1 até o índice N, comparando o valor guardado com a chave de busca digitada pelo usuário:

graph TD
    A["Chave de Busca: 'PN-295-80'"] --> B["1. Compara com vetor[1]"]
    B -- "Diferente" --> C["2. Compara com vetor[2]"]
    C -- "Diferente" --> D["3. Compara com vetor[3]"]
    D -- "IGUAL! (Encontrou)" --> E["1. Marca Flag: achou <- VERDADEIRO<br/>2. Exibe Dados da Peça<br/>3. Guarda Posição"]
    D -- "Diferente" --> F["... até o final do vetor"]
    F --> G{achou = FALSO?}
    G -- "Sim" --> H["Exibe: 'Item Não Localizado!'"]
    
    style A fill:#8e44ad,stroke:#fff,stroke-width:2px,color:#fff
    style D fill:#f39c12,stroke:#fff,stroke-width:2px,color:#fff
    style E fill:#217346,stroke:#fff,stroke-width:2px,color:#fff
    style H fill:#c0392b,stroke:#fff,stroke-width:2px,color:#fff

2. O Padrão da Flag Booleana (Evitando o Erro Mais Comum!)

O Erro Clássico do Programador Iniciante:
Se você colocar escreval("Não encontrado") dentro do senao do laço de repetição, o programa imprimirá “Não encontrado” 100 vezes para cada elemento diferente antes de achar o correto!

A Solução Profissional:

  1. Inicialize uma flag antes do laço: achou <- FALSO.
  2. Se encontrar o item dentro do laço: achou <- VERDADEIRO.
  3. Depois que o laço terminar, teste: se (nao achou) entao escreval("Não encontrado").

3. O Algoritmo para Encontrar o Maior e o Menor Valor

Para encontrar o maior valor em uma lista:

  1. Assuma provisoriamente que o primeiro elemento (vetor[1]) é o maior de todos (maior <- vetor[1]).
  2. Percorra do elemento 2 até N com o laço para.
  3. Se encontrar qualquer elemento maior que o atual (se vetor[i] > maior), atualize a variável maior e guarde o índice posicaoMaior <- i.

O algoritmo do menor valor é exatamente o mesmo raciocínio, só invertendo a comparação:

  1. Assuma provisoriamente que o primeiro elemento é o menor (menor <- vetor[1]).
  2. Percorra do elemento 2 até N.
  3. Se encontrar qualquer elemento menor que o atual (se vetor[i] < menor), atualize menor e guarde posicaoMenor <- i.

📖 Exemplo Guiado: Localizador de Peças com Flag Booleana

Código do Algoritmo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

algoritmo "Buscador_Pecas_FastLog"
var
   codigos : vetor [1..5] de caractere
   quantidades : vetor [1..5] de inteiro
   precos : vetor [1..5] de real
   i, pos : inteiro
   codigoBusca : caractere
   encontrado : logico

inicio
   // 1. Inicialização da Base de Dados em Memória
   codigos[1] <- "PN-295-80" ; quantidades[1] <- 14 ; precos[1] <- 1850.00
   codigos[2] <- "OL-15W40"; quantidades[2] <- 45 ; precos[2] <- 32.50
   codigos[3] <- "FT-AR"  ; quantidades[3] <- 8  ; precos[3] <- 120.00
   codigos[4] <- "LT-COMB" ; quantidades[4] <- 30 ; precos[4] <- 75.00
   codigos[5] <- "PA-FREIO"; quantidades[5] <- 12 ; precos[5] <- 450.00

   escreval("==========================================")
   escreval("     FASTLOG - BUSCADOR DE ALMOXARIFADO   ")
   escreval("==========================================")
   escreva("Digite o código da peça para consultar: ")
   leia(codigoBusca)

   // 2. Algoritmo de Busca Linear com Flag
   encontrado <- FALSO

   para i de 1 ate 5 faca
      se (codigos[i] = codigoBusca) entao
         encontrado <- VERDADEIRO
         pos <- i
      fimse
   fimpara

   // 3. Avaliação Final Fora do Laço
   escreval("")
   se (encontrado) entao
      escreval(">> [PEÇA LOCALIZADA COM SUCESSO!]")
      escreval("   Código SKU : ", codigos[pos])
      escreval("   Posição    : Gaveta/Prateleira #", pos)
      escreval("   Saldo Real : ", quantidades[pos], " unidades")
      escreval("   Preço Unit.: R$ ", precos[pos]:8:2)
   senao
      escreval(">> [AVISO]: Peça com código '", codigoBusca, "' não foi localizada.")
   fimse
   escreval("==========================================")
fimalgoritmo

✅ Exemplo de Execução no Console (F9):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

==========================================
     FASTLOG - BUSCADOR DE ALMOXARIFADO   
==========================================
Digite o código da peça para consultar: PA-FREIO

>> [PEÇA LOCALIZADA COM SUCESSO!]
   Código SKU : PA-FREIO
   Posição    : Gaveta/Prateleira #5
   Saldo Real : 12 unidades
   Preço Unit.: R$   450.00
==========================================

🛠️ Prática Obrigatória 1: Campeão de Quilometragem da Frota

Passo 1: O Desafio

Crie um algoritmo "Campeao_KM" que receba o nome e a quilometragem rodada no mês por 5 motoristas da empresa (usando dois vetores paralelos). Ao final, o programa deve:

  1. Descobrir qual motorista rodou a maior quilometragem (o algoritmo do maior, visto nos Fundamentos).
  2. Descobrir também qual motorista rodou a menor quilometragem (o algoritmo do menor, visto nos Fundamentos).
  3. Exibir o nome e a quantidade exata de KM tanto do campeão quanto do motorista com menor produtividade.

✅ Resultado Esperado (Prática 1):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

Nome do Motorista [1]: Carlos
Quilometragem (KM) [1]: 4200
Nome do Motorista [2]: Mariana
Quilometragem (KM) [2]: 5800
Nome do Motorista [3]: Tiago
Quilometragem (KM) [3]: 3100
Nome do Motorista [4]: Fernanda
Quilometragem (KM) [4]: 4900
Nome do Motorista [5]: Wilson
Quilometragem (KM) [5]: 5200

=============================================
CAMPEÃO DE PRODUTIVIDADE : Mariana
TOTAL RODADO NO MÊS      : 5800.00 km
---------------------------------------------
MENOR PRODUTIVIDADE      : Tiago
TOTAL RODADO NO MÊS      : 3100.00 km
=============================================

🛠️ Prática Obrigatória 2: Filtro de Cargas Super-Pesadas (> 10 Toneladas)

Crie um algoritmo "Filtro_Cargas_Pesadas" que leia o peso de 6 caminhões na balança e armazene em um vetor. Em seguida, o programa deve:

  1. Contar quantos caminhões pesam mais de 10.000 kg.
  2. Exibir a listagem apenas dos caminhões que ultrapassaram esse peso de corte.

✅ Resultado Esperado (Prática 2):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

=== ENTRADA DE DADOS DA BALANÇA ===
Peso do Veículo #1 (kg): 8500
Peso do Veículo #2 (kg): 12300
Peso do Veículo #3 (kg): 9800
Peso do Veículo #4 (kg): 15000
Peso do Veículo #5 (kg): 7200
Peso do Veículo #6 (kg): 11000

=== VEÍCULOS DE ALTA TONELAGEM (> 10.000 KG) ===
-> Veículo #2 | Peso: 12300.00 kg
-> Veículo #4 | Peso: 15000.00 kg
-> Veículo #6 | Peso: 11000.00 kg
------------------------------------------------
Total de Veículos Super-Pesados: 3 de 6 inspecionados.

📤 Instruções de Entrega (Microsoft Teams)

  1. Salve o arquivo como: Atividade_14_SeuNome_SeuSobrenome.alg.
  2. Teste o código buscando itens existentes e inexistentes para validar a flag.
  3. No Microsoft Teams, envie na tarefa “VisuAlg Cap 14 - Pesquisa em Vetores”.
  4. Clique em Entregar (Turn In).

💡 Checkpoint de Lógica & Engenharia de Software

Você acabou de aplicar o algoritmo fundamental de Busca Linear ($O(N)$). Em bancos de dados relacionais (SQL), quando uma coluna não possui um índice B-Tree criado, o motor do banco executa exatamente uma busca linear (Table Scan / Full Scan) percorrendo todas as linhas da tabela.

🔥 Desafio de Fixação: Menor Frete e Média da Frota

Modifique o algoritmo de quilometragem para encontrar simultaneamente o Motorista que mais rodou e o Motorista que menos rodou, exibindo também a média de KM de toda a equipe.

🔑 Gabarito de Código Completo

Prática 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

algoritmo "Campeao_KM"
var
   nomes : vetor [1..5] de caractere
   km : vetor [1..5] de real
   i, posMaior, posMenor : inteiro
   maiorKm, menorKm : real
inicio
   escreval("=== REGISTRO MENSAL DE QUILOMETRAGEM ===")
   para i de 1 ate 5 faca
      escreva("Nome do Motorista [", i, "]: ") leia(nomes[i])
      escreva("Quilometragem (KM) [", i, "]: ") leia(km[i])
   fimpara

   // Algoritmo de Localização do Maior e do Menor
   maiorKm <- km[1]
   posMaior <- 1
   menorKm <- km[1]
   posMenor <- 1

   para i de 2 ate 5 faca
      se (km[i] > maiorKm) entao
         maiorKm <- km[i]
         posMaior <- i
      fimse
      se (km[i] < menorKm) entao
         menorKm <- km[i]
         posMenor <- i
      fimse
   fimpara

   escreval("")
   escreval("=============================================")
   escreval("CAMPEÃO DE PRODUTIVIDADE : ", nomes[posMaior])
   escreval("TOTAL RODADO NO MÊS      : ", maiorKm:8:2, " km")
   escreval("---------------------------------------------")
   escreval("MENOR PRODUTIVIDADE      : ", nomes[posMenor])
   escreval("TOTAL RODADO NO MÊS      : ", menorKm:8:2, " km")
   escreval("=============================================")
fimalgoritmo

Prática 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

algoritmo "Filtro_Cargas_Pesadas"
var
   pesos : vetor [1..6] de real
   i, totalPesados : inteiro
inicio
   totalPesados <- 0

   escreval("=== ENTRADA DE DADOS DA BALANÇA ===")
   para i de 1 ate 6 faca
      escreva("Peso do Veículo #", i, " (kg): ")
      leia(pesos[i])
   fimpara

   escreval("")
   escreval("=== VEÍCULOS DE ALTA TONELAGEM (> 10.000 KG) ===")
   para i de 1 ate 6 faca
      se (pesos[i] > 10000.0) entao
         totalPesados <- totalPesados + 1
         escreval("-> Veículo #", i, " | Peso: ", pesos[i]:8:2, " kg")
      fimse
   fimpara

   escreval("------------------------------------------------")
   escreval("Total de Veículos Super-Pesados: ", totalPesados, " de 6 inspecionados.")
fimalgoritmo

Desafio:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

algoritmo "Maior_Menor_Media"
var
   nomes : vetor [1..5] de caractere
   km : vetor [1..5] de real
   i, posMaior, posMenor : inteiro
   maiorKm, menorKm, somaKm, mediaKm : real
inicio
   somaKm <- 0.0

   para i de 1 ate 5 faca
      escreva("Motorista [", i, "]: ") leia(nomes[i])
      escreva("KM [", i, "]: ") leia(km[i])
      somaKm <- somaKm + km[i]
   fimpara

   maiorKm <- km[1] ; posMaior <- 1
   menorKm <- km[1] ; posMenor <- 1

   para i de 2 ate 5 faca
      se (km[i] > maiorKm) entao
         maiorKm <- km[i]
         posMaior <- i
      fimse
      se (km[i] < menorKm) entao
         menorKm <- km[i]
         posMenor <- i
      fimse
   fimpara

   mediaKm <- somaKm / 5.0

   escreval("")
   escreval("MAIOR KM : ", nomes[posMaior], " com ", maiorKm:8:2, " km")
   escreval("MENOR KM : ", nomes[posMenor], " com ", menorKm:8:2, " km")
   escreval("MÉDIA KM : ", mediaKm:8:2, " km por veículo")
fimalgoritmo

📝 Atividade Extra: Questionário de Fixação (Caderno)

Instruções: Responda no caderno, de próprio punho, as 10 perguntas abaixo com base no que foi estudado neste capítulo. Ao concluir, leve o caderno até o professor para correção e visto.

  1. Como funciona o algoritmo de Busca Linear (Linear Search), segundo a explicação dos Fundamentos deste capítulo?
  2. Qual é o erro clássico do programador iniciante descrito no aviso de atenção, ao colocar escreval("Não encontrado") dentro do senao de um laço de busca?
  3. Descreva os três passos da solução profissional com flag booleana para evitar esse erro.
  4. Descreva o algoritmo para encontrar o maior valor em uma lista, conforme os passos apresentados nos Fundamentos.
  5. No Cenário Prático, quais três informações o sistema deve responder quando um mecânico busca uma peça no almoxarifado?
  6. No algoritmo Buscador_Pecas_FastLog, quantos vetores paralelos são usados para armazenar os dados de cada peça, e quais são eles?
  7. Na Prática Obrigatória 1 (Campeao_KM), quantos motoristas são registrados, e o que o programa deve descobrir ao final?
  8. Na Prática Obrigatória 2 (Filtro_Cargas_Pesadas), qual é o peso de corte (em kg) usado para classificar um caminhão como “super-pesado”?
  9. Segundo o Checkpoint de Lógica, a que operação de bancos de dados relacionais (SQL) a busca linear corresponde quando uma coluna não possui um índice B-Tree?
  10. No código Buscador_Pecas_FastLog, por que o teste se (encontrado) entao e o uso da variável pos são feitos depois que o laço para termina, e não dentro dele?