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
   indice=-1;
   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 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.

#include <stdio.h>

int busca_linear_inef(int v[], int n, int x)
{
    int i, indice;
    indice = -1;
    for(i=0;i<n;i++) {
        if (v[i] == x)
            indice = i;
    }
    return indice;
}

int busca_linear_efv1(int v[], int n, int x)
{
    int i;

    for(i=0;i<n;i++) {
        if (v[i] == x)
            return i;
    }
    return -1;
}

int busca_linear_efv2(int v[], int n, int x)
{
    int i, indice;
    indice = -1;
    for(i=0;i<n;i++) {
        if (v[i] == x) {
            indice = i;
            break;
        }
    }
    return indice;
}

int main()
{
    int alfa[5]={31,97,156,91,8};
    int pos;
    pos=busca_linear_efv2(alfa,5,156);
    printf("O item 156 está na posicao %d\n", pos);
    pos=busca_linear_efv2(alfa,5,230);
    printf("O item 230 está na posicao %d\n", pos);
    return 0;
}

Busca Linear com Sentinela

Esta versão da busca linear visa eliminar um dos dois testes realizados no "loop" da verão anterior. Note que a cada iteração existe um teste devido ao comando de repetição 'for' (teste de se i < n) e um teste de verificação de ocorrência do item (if (v[i] == x)).

Na vesão com sentinela o item é colocado no final do array, substituindo o último elemento do array. Obviamente, este elemento deve ser salvo.

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 AUXILIARES
  inteiro i,
  ultimo;
INÍCIO
   ultimo = A[n-1] /* salva o último na variável auxiliar */
   i=0;
   ENQUANTO A[i] != x FAÇA  /* procura pelo elemento - observe que em algum momento ele será encontrado... */
         incremente i

   SE i<n-1 OU A[n-1]==ultimo
         retorna i
   SENAO
         retorna -1   /* não encontrado */ 
 
FIM

EXERCÍCIO 4

Implementar em C uma função para realizar busca linear com sentinela.