ATIVIDADE A1 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO

Prévia do material em texto

Para exemplificarmos uma busca sequencial, podemos usar itens de dados 
armazenados em uma coleção, como uma lista, onde podemos dizer que eles 
têm uma relação linear ou sequencial. Cada item de dados é armazenado em 
uma posição relativa aos outros. Nas listas, essas posições relativas são os 
valores de índice dos itens individuais. Como esses valores de índice são 
ordenados, é possível para nós visitá-los em sequência. Este processo dá 
origem a nossa primeira técnica de busca, a busca sequencial. 
A função precisa da lista e do item que procuramos e retorna um valor booleano 
para saber se ele está presente. A variável booleana encontrada é inicializada 
para falso e é atribuído o valor verdadeiro se descobrimos o item na lista. 
No melhor caso, o elemento a ser buscado é encontrado logo na primeira 
tentativa da busca. No pior caso, o elemento a ser buscado encontra-se na última 
posição e são feitas N comparações, sendo N o número total de elementos. No 
caso médio, o elemento é encontrado após (N+1)/2 comparações. O algoritmo 
de busca linear é um algoritmo O(n). 
Já na busca binária, caso você possua uma lista com os valores ordenados de 
forma numérica ou alfabética, é possível fazer uma busca muito mais rápida. Ao 
invés de pesquisar a lista em sequência, uma busca binária começará 
examinando o item do meio. Se esse item for aquele que estamos procurando, 
a busca termina. Se não for o item correto, podemos usar a natureza ordenada 
da lista para eliminar a metade dos itens restantes. Se o item que procuramos 
for maior do que o item do meio, sabemos que toda a metade inferior da lista, 
bem como o item do meio, podem ser eliminados de uma consideração mais 
aprofundada. O item, se estiver na lista, deve estar na metade superior. 
Podemos então repetir o processo com a metade superior. Comece no item do 
meio e compare-o contra o que estamos procurando. Novamente, encontramos 
ou dividimos a lista pela metade, eliminando assim uma grande parte do nosso 
possível espaço de busca. 
Com base nos exemplos citados, podemos concluir que para se ter uma maior 
eficiência no nosso algoritmo, a busca binária seria a melhor escolha, pois, 
sabendo que de alguma forma encontraremos o nosso resultado, ela será 
interrompida assim que isso for verdadeiro, já a busca sequencial, mesmo 
sabendo que ela buscará por todo o espaço de pesquisa, independente do 
resultado de sua busca, é mais indicada para casos onde o programador não 
sabe exatamente se o seu alvo encontra-se neste range de pesquisa.