Tópicos Adicionais I

Objteivos

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;
INÍCIO
   i=-1 /* deixa preparado com valor -1 significando que o item NÃO foi encontrado */
   PARA cada I variando de 0 a N-1 FAZ
      SE V[i] != X ENTÃO 
         indice = i;
   retorna indice
FIM

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

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