Estrutura de dados: Primeiros passos com métodos de busca

Este artigo trata da recuperação de dados a partir de um conjunto de informações previamente armazenado.

Em geral, no meio computacional, a informação é dividida em registros e cada registro possui uma chave para ser usada na pesquisa e uma ou mais informações de interesse do usuário.

Por exemplo, o registro de um aluno em uma universidade pode conter uma chave que identifica unicamente a matrícula e um conjunto de informações sobre este aluno, como nome, endereço, telefone, entre outros.

O objetivo da pesquisa é encontrar uma ou mais ocorrências de registros com chaves iguais à chave de pesquisa e para essa finalidade existem vários métodos.

A escolha do mais adequado depende, principalmente: (i) da quantidade de dados envolvidos; e (ii) da possibilidade de o arquivo sofrer inserções e/ou retiradas.

Por exemplo, é diferente encontrar o registro do nome de um estado brasileiro no conjunto de todos os estados brasileiros e encontrar o registro de um aluno que fez o Exame Nacional do Ensino Médio (ENEM).

No segundo caso, a massa de dados é muito maior. Também é diferente procurar um registro em um conjunto de dados que sofre poucas alterações (inserções/remoções) como, por exemplo, o conjunto de estados brasileiros; e procurar por uma venda, a partir do seu código, na base de dados de uma grande empresa de e-commerce, cujos dados mudam constantemente.

No primeiro caso, o importante é minimizar o tempo de pesquisa sem preocupação com o tempo necessário para realizar inserções e remoções no conjunto de dados, uma vez que o mesmo sofre poucas alterações ao longo do tempo.

A partir disso, neste artigo analisaremos conceitos, na teoria e na prática, da pesquisa interna (ou busca interna), na qual assume-se que o conjunto de dados a ser pesquisado é pequeno o suficiente para ser carregado de uma vez na memória principal (ou memória interna) do computador.

Quando a quantidade de informações é grande o suficiente a ponto de não ser possível tratá-la de uma vez na memória principal, métodos de pesquisa externa são necessários. Esse tipo de método é capaz de lidar com conjuntos de dados que estão armazenados na memória auxiliar (externa) do computador, como o HD, fitas magnéticas, entre outros.

A prioridade de cada categoria de algoritmos é diferente. Enquanto em uma pesquisa interna procura-se reduzir a quantidade de comparações realizadas pelo método escolhido, na pesquisa externa, além desse requisito, deve-se levar em consideração a quantidade de consultas ao disco necessárias para se encontrar a informação pesquisada.

Abordaremos três métodos de busca interna: sequencial, binária e utilizando a tabela Hash. No tópico “Conceitos Preliminares” apresentaremos o modelo de estrutura de dados que será utilizado para a implementação dos métodos de pesquisa.

Em seguida, nos tópicos “Pesquisa Sequencial”, “Pesquisa Binária” e “Pesquisa por Tabela Hash”, serão analisados os três principais métodos de pesquisa existentes na literatura, destacando suas principais características e estratégias de implementação e eficiência.

Conceitos preliminares

Este tópico apresenta alguns conceitos que são fundamentais para o acompanhamento deste artigo, tal como o conceito de análise da complexidade de algoritmos, que será amplamente discutido, e o conceito de “Dicionário”, como um tipo abstrato de dados para implementação de métodos de pesquisa.

A análise da complexidade de algoritmos

Um aspecto predominante na escolha de um método de pesquisa é o tempo gasto para realizá-las, bem como para manipular o conjunto de dados, inserindo ou removendo elementos.

Para a pesquisa, a medida de complexidade relevante consiste no número de comparações entre chaves realizadas até que uma resposta seja dada pelo algoritmo.

Quanto à inserção/remoção, leva-se em consideração também o número de movimentações (ou trocas) necessárias para acomodar um novo item ou remover um item existente do conjunto de da ...