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 dados.

Assim, as medidas de complexidade analisadas para cada método de pesquisa apresentado neste texto são C(n) e M(n), que correspondem, respectivamente, às funções de complexidade que descrevem o número de comparações e o número de movimentações realizadas por cada método, onde n é a quantidade de itens do conjunto de dados a ser pesquisado.

É importante ressaltar ainda que a maioria dos métodos de pesquisa é sensível à ordem inicial dos itens a serem pesquisados, isto é, o número de comparações e/ou movimentações realizadas por um método pode variar caso o conjunto esteja ordenado ou não ou se o elemento a ser pesquisado estiver no início ou no final do conjunto, entre outros. Assim, C(n) e M(n) devem ser considerados, sempre quando possível, para três casos:

• O melhor caso: corresponde ao menor número de comparações/movimentações sobre todas as possíveis entradas de tamanho n;
• O pior caso: corresponde ao maior número de comparações/movimentações sobre todas as possíveis entradas de tamanho n;
• O caso médio (ou caso esperado): corresponde à média do número de comparações/movimentações de todas as possíveis entradas de tamanho n.

O tipo abstrato de dados Dicionário

É muito importante considerar métodos de pesquisa como um Tipo Abstrato de Dado – TAD, isto é, uma estrutura de dados com um conjunto de operações associado a ela.

O motivo é que um TAD promove a independência dos possíveis tipos de implementação para esses métodos de pesquisa. Por exemplo, um programador pode implementar o método de pesquisa sequencial com vetores, outro pode utilizar listas encadeadas, mas de qualquer forma, todos os casos tratam do mesmo propósito (a pesquisa) e devem oferecer as mesmas funções aos seus usuários.

Um TAD comumente utilizado para pesquisa é o dicionário. Um dicionário é um TAD cujas operações são responsáveis por inicializar a estrutura de dados utilizada no dicionário, pesquisar um ou mais registros com determinada chave, inserir um novo registro e remover um registro específico.

A implementação dos métodos de pesquisa apresentados neste texto baseia-se no TAD dicionário e na linguagem de programação Java. Para simplificar a apresentação dos métodos de pesquisa, apenas as funções " [...] continue lendo...