Parâmetros para a realização dos testes computacionais

1. Busca

A hipótese básica assumida no processo de busca é que o conjunto de dados, dentre o qual um determinado elemento deve ser procurado, possui tamanho fixo com N posições:

item a[N];

onde item representa uma estrutura de dados contendo um campo que atua como chave para a pesquisa e N é uma constante indicando o número de elementos. No nosso trabalho, utilizamos de um Array List para criar a estrutura com a quantidade de elementos (números aleatórios) escolhida pelo usuário. Após, convertemos a estrutura para um array inteiro de tamanho N.

Figura 1 Conversão de Array List para array inteiro

O objetivo da busca é encontrar a key em alguma posição da estrutura:

a[i]= = key

Para fornecer os elementos a estrutura, utilizamos dos dados da Tabela 1. Sendo N o número de números gerados, low a faixa inferior de número a ser gerado, high é a faixa superior, seed:

N low high seed

100 0 100000 1234554321

1000 0 100000 1234554321

10000 0 100000 1234554321

100000 0 100000 1234554321

Tabela 1: Parâmetros para a realização dos testes computacionais.

Através destes parâmetros, geramos os números aleatórios:

Figura 2 Objetos e métodos utilizados para a geração e obtenção dos números aleatórios

Vários métodos e estruturas de dados podem ser empregados para se fazer buscas. Implementamos todos eles retornando -1 caso não encontre o elemento procurado.

2. Tipos de busca

2.1. Busca linear ou sequencial

O método de pesquisa mais simples que existe. Funciona da seguinte forma: a partir do primeiro registro, pesquise sequencialmente até encontrar a chave procurada; então pare.

A função realizaBuscaLinear retorna o índice do registro que contém a chave x; caso não esteja presente o valor retornado é -1. Observe que esta implementação não suporta mais de um registro com uma mesma chave. Para aplicações com esta característica é necessário incluir um argumento a mais na função de pesquisa para conter o índice a partir do qual se quer pesquisar, e alterar a implementação de acordo.

2.1.1. Análise

A grande vantagem desse método de busca é que, além de se tratar de um algoritmo simples, os dados que serão analisados não precisam passar por nenhum tipo de preparo (como a ordenação, por exemplo) antes de execução do algorítimo, tornando seu uso extremamente simples e confiável. É mais eficiente quando a estrutura possui poucos elementos.

2.1.2. Testes

Figura 3 Teste de busca linear

2.2. Busca linear com sentinela

A idéia básica é fazer com que o elemento procurado (x) sempre seja encontrado. Para isso, introduz-se o elemento adicional no final da estrutura (a[]). Um registro sentinela contendo a chave de pesquisa é colocado após a última posição do array. Esta técnica garante que a pesquisa sempre termina. Após a chamada da função Pesquisa, se o índice é zero, significa que a pesquisa foi sem sucesso.

Figura 4 Acrescentando sentinela e realizando busca

2.2.1. Análise

O uso da sentinela tem como objetivo acelerar a busca, através da simplificação da expressão booleana, ou seja, a sentinela proporciona a oportunidade de polpar a execução de um condicional.

2.2.2. Testes

Figura 5 Teste de busca linear com sentinela

2.3. Busca Binária

Se não sabemos nada a respeito da ordem em que os itens aparecem no vetor, o melhor que podemos fazer é uma busca linear. Entretanto, se os itens aparecem ordenados5, podemos usar um método de busca muito mais eficiente. Esse método é semelhante aquele que usamos quando procuramos uma palavra num dicionário: primeiro abrimos o dicionário numa página aproximadamente no meio; se tivermos sorte de encontrar a palavra nessa página, ótimo; senão, verificamos se a palavra procurada ocorre antes ou

depois da página em que abrimos e então continuamos, mais ou menos do mesmo jeito, procurando a palavra na primeira ou na segunda metade do dicionário.

Como a cada comparação realizada, o espaço de busca reduz-se aproximadamente

à metade:

Figura 6 Funcionamento de uma busca binária

Caso a busca tenha que continuar, podemos proceder exatamente da mesma maneira: verificamos o item existente no meio da metade escolhida e se ele ainda não for aquele que procuramos, continuamos procurando no meio do quarto escolhido, depois no meio do oitavo e assim por diante até que o item procurado seja encontrado ou que não haja mais itens a examinar.

Como em cada passo o intervalo de busca reduz-se aproximadamente à metade,

é evidente que o processo de busca binária sempre termina, mesmo que

o item procurado não conste do vetor.

Nesse caso, porém, o processo somente

termina quando não há mais itens a examinar, ou seja, quando o intervalo

de busca fica vazio.

No nosso caso, usamos as variáveis low, middle e high:

Figura 7 Código de busca binária

2.3.1. Análise

Ao contrário da busca linear, a busca binária somente funciona corretamente se o vetor estiver ordenado. Isso pode ser uma desvantagem. Entretanto, à medida em que o tamanho do vetor aumenta, o número de comparações feitas pelo algoritmo de busca binária