trab

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