Tópicos Adicionais I

ReferÊncias

CORMEN, Thomas. Desmistificando Algoritmos. [Digite o Local da Editora]: Grupo GEN, 2013. 9788595153929. Disponível em: https://app.minhabiblioteca.com.br/#/books/9788595153929/. Acesso em: 12 abr. 2022.

Objetivos

Após esta aula o aluno deverá ser capaz de:

• Explicar o funcionamento de um algoritmo de busca linear em vetor
• Aplicar a busca em problemas práticos.

Busca Linear Simples em vetor - Modo Ineficiente

Trata-se de um algoritmo que busca um determinado item armazenado em um vetor. O algoritmo realiza uma busca desde o início do vetor até o final, comparando item por item.

Suponha um vetor que armazena somente números inteiros POSITIVOS (incluindo 0). Uma busca linear neste

FUNCAO busca_linear
DADOS DE ENTRADA:
   V: Vetor de itens /* para manter conformidade com o C, assumimos que a indexação começa em 0 */
   inteiro n: tamanho do vetor
   inteiro x: valor a ser procurado
DADOS DE SAÍDA
   inteiro indice: índice do item encontrado (-1 se não encontrado)
VARIÁVEIS
  inteiro i,
          indice;
INÍCIO
   PARA cada i variando de 0 a N-1 FAZ
      SE V[i] == X ENTÃO 
         indice = i;
   SE I==N
       retornar -1
   SENÃO 
       retorna indice
FIM

Discussão: por que esta solução é ineficiente?

Exercício 1: Implementar em sala a função acima usando a Linguagem C. Demonstrar o resultado para pelo menos 4 vetores de tamanhos diferentes. Inicie estes vetores com valores para evitar entrada de dados com scanf.

Busca Linear Simples em vetor - Versão mais eficiente mas com elementos "destruturantes"

O algoritmo acima pode ser melhorado com um retorno ou interrupção assim que o item for encontrado. Em C pode-se também interromper o laço com o comando break.

Exercício 2: Modificar o exercício anterior usando um return dentro do laço

Exercício 3: Modificar o exercício anterior usando um break para interromper o laço.