Índice > Lista > Estática Seqüencial > Algoritmos de Busca

Instituto de Ciências Matemáticas e de Computação 
Departamento de Computação e Estatística 
SCE182 - Algoritmos e Estruturas de Dados 1 
Profs. Resp.: Graça Pimentel, Maria Cristina e Rosane Minghim

Algoritmos de Busca em Lista Estática Seqüencial

1) Listas sequenciais não ordenadas

Seja L uma lista linear não ordenada alocada sequencialmente

    type registro = record
                                chave: T1;
                                info: T2;
                            end;

    type Lista = record
                            Nelem: integer;
                            A: arrray [1..n] of registro;
                        end; 

  Var L: Lista;
A função busca1 abaixo busca um registro contendo a chave x na lista L, e retorna o índice do registro se encontrado, caso contrário retorna zero. 
  Function  busca1(L:Lista; x:T1; VAR achado:registro);
    Var i: 1..Max;

    Begin
      i := 1;
      busca1 := 0;            {elemento não encontrado}
      While i <= L.Nelem do
        If L.A[i].chave = x then
          Begin
            busca1 := i;
            achado := L.A[i];
            i := L.Nelem + 1;   {termina loop}
          End
        Else i := i+1;
    End;
Em busca1( ), para cada elemento dois testes são realizados
  1. i <= L.Nelem
  2. L.A[i].chave = x.
Alterar o algoritmo acima para que os dois testes sejam tratados na condição do 'while', de forma a evitar o 'término forçado' do loop (sentença em verde no algoritmo).

O processo acima pode ser melhorado com o uso do seguinte artifício (chamado 'sentinela'):

  • É criado um novo registro no final da lista, chamado de sentinela, que contém a chave procurada.
  • A busca é realizada sabendo-se que um registro contendo a chave vai ser encontrado.
  • Ao final verifica se o registro encontrado é o sentinela.
  • Deste modo o teste duplo para cada elemento é evitado.
  • A lista L, neste caso, deve poder conter um registro extra.
    •   Function  busca1(L:Lista; x:T1; VAR achado:registro);
    VAR i: 1..Max;

    begin
      L.A[L.Nelem+1].chave = x;      {insere elemento sentinela}
      i := 1;
      While (L.A[i].chave <> x)  do
        i := i+1;
      {checa se encontrado é o sentinela}
      If (i = L.Nelem + 1) Then
        busca := 0;
          Else
          Begin
        busca := i;
      achado := L.A[i];
          End;
    End;

    2) Listas sequenciais ordenadas

    No caso de listas ordenadas, deve-se aproveitar o fato de que nem sempre é necessário percorrer a lista toda para concluirmos que elemento não está na lista.
    A versão do algoritmo de busca com sentinela para listas ordenadas é: 
      Function busca_ord(L:Lista; x:T1; var achado:registro);
    var i: 1..Max;

    Begin
      L.A[L.Nelem+1].chave := x;    {insere elemento sentinela}
      i := 1;
      While (L.A[i].chave < x) do  {compara-se apenas os menores}
        i := i+1;
      If (i = L.Nelem + 1) or i(L.A[i].chave <> x) Then 
        busca := 0
      Else
          Begin 
        busca := i;
            achado:= L.A[i];
          End;
    End;
    O fato de se utilizar o recurso da sentinela na busca sequencial, acima, elimina a necessidade de testar, para cada elemento, se o final da lista é alcançado ou não.

    No caso de listas ordenadas, pode-se apresentar um algoritmo BEM mais eficiente - o qual tira MUITO MAIS proveito do fato da lista estar ordenada!

    O algoritmo de busca binária tem como idéia básica o fato de que, dada uma posição dentro da lista, o elemento procurado vai estar ou antes ou depois desta posição, e, portanto, não se precisa procurar dos dois lados.

    Numa dada lista ordenada:

  • Compara-se o elemento procurado com o registro do meio da lista, para saber se o elemento estaria na metade superior ou inferior da lista.
  • Repete-se esse processo até encontrar o elemento ou esgotar a lista.
    •   Function busca_bin(L:Lista; x:T1; var achado:registro);
    var inf, sup, meio: índices;

    Begin
      inf := 1;
      sup := L.Nelem;
      busca_bin := 0;
      While inf <= sup do
        Begin
          meio := [(inf + sup) div 2];
          If L.A[meio].chave = x then
            Begin
              busca_bin := meio;
              inf := sup + 1;
            End
          Else
            If (L.A[meio].chave < x) Then 
              inf := meio + 1
            Else 
              sup := meio -1;
        End;
    End;
        -> determinar quem é 'achado' no algoritmo acima
        -> alterar o algoritmo acima para eliminar o teste de igualdade deentro
           do loop, mantendo sua consistência. Determinar quem é o 'achado' no novo
           algoritmo.
        -> Desenvolver algoritmos de Busca para lista estática Encadeada, com e sem ordenação.
    Operações Básicas
    Exercício