Algoritmos de Pesquisa e Estruturas de Listas

5 – ALGORITMOS DE PESQUISA (OU BUSCA): São dois os métodos de pesquisa, ou busca, por uma ocorrência de um elemento dentro de um arranjo de dados que são mais comumente usados. Geralmente é o usuário da aplicação quem fornece o valor do elemento que está procurando e que tem interesse na pesquisa. Esses dois métodos são: a pesquisa sequencial e a pesquisa binária. Qual desses tipos de pesquisa apresenta o melhor resultado? Depende exclusivamente da quantidade de operações realizadas para encontrar determinado elemento no arranjo, e isso é determinado por dois fatores: o número de elementos do arranjo e a quantidade de consultas que se faça no arranjo. Após conhecer como funcionam os dois tipos de pesquisa, no próximo capítulo serão apresentados alguns cálculos sobre como calcular a quantidade de operações necessárias para encontrar (ou não) um elemento dentro do arranjo de dados e, com isso, poder decidir qual dos métodos é melhor aplicar.

Pesquisa Sequencial

O método de pesquisa sequencial consiste em efetuar a busca da informação desejada a partir do primeiro elemento, percorrendo o vetor sequencialmente até o último elemento. Localizando a informação procurada em algum dos elementos, esta é apresentada ao usuário e encerra-se a busca. Este método de pesquisa é, na média, um tanto lento, porém, eficiente nos casos em que o vetor contenha seus elementos de forma desordenada.

Pesquisa Binária

O método da pesquisa binária apresenta um mecanismo que, na média, se mostra mais rápido em comparação ao método da pesquisa sequencial. Uma diferença é que para aplicar a pesquisa binária o arranjo de dados deve estar obrigatoriamente ordenado previamente. Depois de ordenado o vetor, este é dividido em duas partes e examinado se a informação a ser pesquisada se encontra na linha de divisão (meio) do vetor ou se está acima ou abaixo desta linha de divisão. Se estiver acima, toda a metade inferior é desprezada para verificação. Em seguida, se a informação não foi encontrada no meio (lembre-se de que o vetor já está ordenado!), novamente se divide esta metade do vetor em duas partes e se examina se a informação está no meio, acima ou abaixo da linha divisória. O processo de divisão e descarte continua até que a informação seja encontrada ou até se acabar os elementos do arranjo.

7 – LISTAS: Uma Lista é uma estrutura de dados que armazena elementos de forma alinhada, ou seja, com elementos dispostos um após o outro, como em uma lista telefônica, um catálogo de peças, entre outros. Além disso, existem vários tipos de listas e o que os determinam é o modo e a política como são realizadas as operações sobre essas listas. As principais operações são, entre outras, inclusão de elementos na lista, acesso a um determinado elemento da lista, exclusão de um elemento, verificação de lista vazia, verificação de lista cheia, quantidade de elementos na lista. A partir de agora praticamente todas as estruturas de dados que serão estudadas são derivadas de algum tipo de lista. As listas podem ser classificadas de várias formas, que dependem de alguns fatores como: o modo como é implementada a alocação de memória; a natureza de manipulação dos elementos da lista e ainda como fica a disposição dos elementos em relação à linearidade ou à hierarquia da estrutura.

Classificação e Tipos de Listas

• Quanto à Linearidade ou Hierarquia da Estrutura:
  • Listas Lineares (Listas Sequenciais, Encadeadas, Pilhas e Filas)
  • Listas Não-Lineares (Árvores)
• Quanto à Alocação de Memória:
  • Estática
  • Dinâmica
• Quanto à Natureza de Manipulação dos Elementos:
  • Sequencial
  • Encadeada