Capítulo 14: Vetores II: Algoritmos de Pesquisa e Filtros (Busca Linear)

🎯 Objetivo da Aula

Guardar dados em vetores é apenas o primeiro passo. O valor real de um sistema reside na sua capacidade de pesquisar, filtrar e auditar esses dados de forma instantânea (como localizar o status de uma entrega pelo código de rastreio ou identificar o motorista com maior quilometragem rodada).

Nesta aula, você aprenderá a:

1. Implementar o algoritmo clássico de Busca Linear (Linear Search) com complexidade $O(N)$.
2. Dominar a técnica da Flag Booleana (logico localizado = falso) para tratamento de itens inexistentes.
3. Desenvolver o algoritmo padrão de localização de Maior e Menor Elemento com retenção de índice.
4. Trabalhar com Vetores Paralelos sincronizados pelo mesmo índice numérico.

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

Situação: A torre de controle da FastLog monitora 5 carretas pesadas. A central armazena os nomes dos 5 motoristas em um vetor (motoristas[5]) e a quilometragem rodada no mês em outro vetor (quilometragem[5]). O supervisor precisa de duas ferramentas urgentes:

1. Localizador Instantâneo: Digitar o nome de um motorista e descobrir imediatamente quantos KM ele rodou.
2. Auditoria do Campeão: Apontar automaticamente quem é o motorista com a Maior Quilometragem Rodada no mês para receber o bônus de eficiência.

Missão: Programar o sistema de auditoria e pesquisa em vetores paralelos da FastLog.

🧠 Fundamentos: Os Algoritmos Clássicos em Vetores

1. O Algoritmo de Busca Linear (Linear Search)

A busca linear percorre o vetor da primeira posição (0) até a última (N-1), comparando cada elemento com a chave pesquisada:

graph TD
    A["Chave de Busca: 'Carlos'"] --> B["Compara com vetor[0]: 'Ana' -> Não"]
    B --> C["Compara com vetor[1]: 'Carlos' -> MATCH!"]
    C --> D["1. Exibe Dados de Carlos<br/>2. Ativa Flag: localizado = verdadeiro<br/>3. Comando pare (Interrompe Busca)"]
    D --> E[Fim da Busca]
    
    style A fill:#8e44ad,stroke:#fff,color:#fff
    style C fill:#27ae60,stroke:#fff,color:#fff
    style D fill:#2980b9,stroke:#fff,color:#fff

2. A Técnica da Flag Booleana

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

logico localizado = falso

para (inteiro i = 0; i < 5; i++) 
{
	se (motoristas[i] == termoBusca) 
	{
		escreva("Encontrado na posição: ", i, "\n")
		localizado = verdadeiro
		pare // Interrompe o laço imediatamente
	}
}

se (nao localizado) 
{
	escreva("Registro não localizado no banco de dados.\n")
}

3. Algoritmo de Maior e Menor Elemento

Para encontrar o maior valor sem errar:

1. Assumimos que o primeiro elemento (vetor[0]) é provisoriamente o campeão.
2. Percorremos do índice 1 em diante: se encontrarmos alguém maior, atualizamos o recorde e a posição!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

real maiorKm = quilometragem[0]
inteiro indiceCampeao = 0

para (inteiro i = 1; i < 5; i++) 
{
	se (quilometragem[i] > maiorKm) 
	{
		maiorKm = quilometragem[i]
		indiceCampeao = i
	}
}

4. Vetores Paralelos

Quando duas ou mais entidades diferentes (o nome de um motorista, a sua quilometragem) precisam ficar associadas, usamos Vetores Paralelos: vetores separados, mas do mesmo tamanho, em que a mesma posição de índice representa sempre o mesmo registro. Por exemplo, motoristas[2] e quilometragem[2] juntos descrevem o terceiro motorista e sua respectiva quilometragem — os dois vetores “andam lado a lado”, sincronizados pelo índice i.

📖 Exemplo Guiado: Painel de Performance de Frota

Código do Programa:

 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
47
48
49
50
51
52
53
54
55

programa 
{
	funcao inicio() 
	{
		// Vetores Paralelos
		cadeia motoristas[5] = {"Carlos Silva", "Beatriz Ramos", "Roberto Dias", "Fernanda Lima", "Wilson Rocha"}
		real quilometragem[5] = {4200.0, 6800.5, 3100.0, 7450.0, 5300.0}

		cadeia termoBusca
		logico localizado = falso

		escreva("==================================================\n")
		escreva("      FASTLOG - PAINEL ANALÍTICO DE FROTAS        \n")
		escreva("==================================================\n\n")

		// 1. Ferramenta de Busca Linear
		escreva("Digite o nome do motorista para consultar KM: ")
		leia(termoBusca)

		para (inteiro i = 0; i < 5; i++) 
		{
			se (motoristas[i] == termoBusca) 
			{
				escreva("\n>> [LOCALIZADO COM SUCESSO]:\n")
				escreva("   Colaborador : ", motoristas[i], "\n")
				escreva("   Quilometragem: ", quilometragem[i], " KM rodados no mês.\n")
				localizado = verdadeiro
				pare // Encerra o laço
			}
		}

		se (nao localizado) 
		{
			escreva("\n>> [AVISO]: Motorista '", termoBusca, "' não consta no cadastro.\n")
		}

		// 2. Auditoria de Maior Produtividade
		real maiorKm = quilometragem[0]
		inteiro indiceCampeao = 0

		para (inteiro i = 1; i < 5; i++) 
		{
			se (quilometragem[i] > maiorKm) 
			{
				maiorKm = quilometragem[i]
				indiceCampeao = i
			}
		}

		escreva("\n--------------------------------------------------\n")
		escreva("CAMPEÃO DE PRODUTIVIDADE DO MÊS:\n")
		escreva("Destaque: ", motoristas[indiceCampeao], " com impressionantes ", maiorKm, " KM!\n")
		escreva("==================================================\n")
	}
}

🛠️ Prática Obrigatória 1: Filtro de Cargas Acima da Média

Passo 1: O Desafio

Crie um programa filtro_cargas.por com um vetor de 5 pesos de carga: real pesos[5] = {1200.0, 4500.0, 800.0, 6200.0, 3100.0}.

1. Calcule a média geral dos pesos.
2. Em um segundo laço, liste apenas os pesos que estão estritamente acima da média.

✅ Resultado Esperado (Prática 1):

1
2
3
4
5

MÉDIA DE PESO DA CARGA: 3160.0 kg
-------------------------------------
CARGAS PESADAS (ACIMA DA MÉDIA):
- Posição [1]: 4500.0 kg
- Posição [3]: 6200.0 kg

🛠️ Prática Obrigatória 2: Localizador de Menor Preço de Frete

Crie um programa menor_frete.por que receba 4 cotações de frete de transportadoras parceiras e informe qual transportadora ofereceu o Menor Preço.

📤 Instruções de Entrega (Microsoft Teams)

1. Salve o arquivo como: Atividade_14_SeuNome_SeuSobrenome.por.
2. Teste a busca com nomes existentes e inexistentes para checar a flag booleana.
3. No Microsoft Teams, envie na tarefa “Portugol Cap 14 - Algoritmos de Busca”.
4. Clique em Entregar (Turn In).

💡 Checkpoint de Lógica & Engenharia de Software

Você acabou de aplicar o algoritmo de Busca Linear ($O(N)$). Em bancos de dados relacionais como PostgreSQL e MySQL, a busca linear corresponde ao famoso Full Table Scan, que é otimizado na indústria através de índices em árvores binárias (B-Trees).

🔥 Desafio de Fixação: Contador de Ocorrências em Vetor

Crie um programa que leia 10 números em um vetor. Peça ao usuário um número e conte quantas vezes esse número se repete dentro do vetor.

🔑 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

programa {
	funcao inicio() {
		real pesos[5] = {1200.0, 4500.0, 800.0, 6200.0, 3100.0}
		real soma = 0.0, media

		para (inteiro i = 0; i < 5; i++) {
			soma += pesos[i]
		}
		media = soma / 5.0

		escreva("MÉDIA DE PESO DA CARGA: ", media, " kg\n")
		escreva("-------------------------------------\n")
		escreva("CARGAS PESADAS (ACIMA DA MÉDIA):\n")

		para (inteiro i = 0; i < 5; i++) {
			se (pesos[i] > media) {
				escreva("- Posição [", i, "]: ", pesos[i], " kg\n")
			}
		}
	}
}

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
26
27

programa {
	funcao inicio() {
		cadeia parceiros[4] = {"TransRápido", "Expresso Sul", "LogNorte", "RodoCargas"}
		real cotacoes[4]

		escreva("=== COTAÇÃO COMPARATIVA DE FRETES ===\n")
		para (inteiro i = 0; i < 4; i++) {
			escreva("Preço do parceiro '", parceiros[i], "' R$: ")
			leia(cotacoes[i])
		}

		real menorValor = cotacoes[0]
		inteiro posMenor = 0

		para (inteiro i = 1; i < 4; i++) {
			se (cotacoes[i] < menorValor) {
				menorValor = cotacoes[i]
				posMenor = i
			}
		}

		escreva("\n-------------------------------------\n")
		escreva("MELHOR OFERTA COMERCIAL:\n")
		escreva("Vencedor: ", parceiros[posMenor], " por apenas R$ ", menorValor, "\n")
		escreva("-------------------------------------\n")
	}
}

Desafio:

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

programa {
	funcao inicio() {
		inteiro numeros[10] = {5, 8, 2, 5, 9, 5, 1, 3, 5, 7}
		inteiro alvo, contagem = 0

		escreva("Digite um número para verificar repetições: ")
		leia(alvo)

		para (inteiro i = 0; i < 10; i++) {
			se (numeros[i] == alvo) {
				contagem++
			}
		}

		escreva("O número ", alvo, " apareceu ", contagem, " vezes no vetor.\n")
	}
}

📝 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. O que é o algoritmo de Busca Linear e qual é a sua complexidade, segundo os Fundamentos do capítulo?
2. Para que serve a técnica da Flag Booleana (ex: logico localizado = falso) dentro do algoritmo de busca?
3. O que faz o comando pare dentro do laço de busca linear apresentado nos Fundamentos?
4. Explique o algoritmo de localização do Maior Elemento: por que assumimos inicialmente que vetor[0] é o “campeão” e a partir de qual índice começamos a comparar os demais valores?
5. O que são “Vetores Paralelos”, segundo o Exemplo Guiado do Painel de Performance de Frota? Cite os dois vetores usados no exemplo.
6. Na Prática Obrigatória 1 (Filtro de Cargas Acima da Média), quais dois passos o programa deve realizar com o vetor de pesos?
7. Na Prática Obrigatória 2 (Localizador de Menor Preço de Frete), quantas cotações de frete o programa deve receber e o que deve ser informado ao final?
8. Segundo o Checkpoint de Lógica & Engenharia de Software, a que operação de bancos de dados relacionais (como PostgreSQL e MySQL) a busca linear corresponde?
9. No algoritmo de busca linear apresentado nos Fundamentos, o que é exibido se, após percorrer todo o vetor, a flag localizado permanecer falso?
10. Dê um exemplo do dia a dia em que você precisaria “procurar” um item específico dentro de uma lista, de forma parecida com a busca do motorista pelo nome no exemplo da FastLog.