GRA0251 Atividade A1

Prévia do material em texto

GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO
Atividade A1
Algoritmos de busca servem para verificar se uma dada informação ocorre em uma sequência ou não.
Um exemplo de algoritmo de busca é o do seguinte enunciado:
Dados uma sequência de números guardados em uma lista seq e um número x, faça uma função que retorne se x ocorre em seq?
Na busca sequencial, a lista toda é percorrida desde o primeiro até o último item, até que se encontre o item buscado. Quando não há mais itens, a conclusão é de que o item buscado não estava presente.
Um exemplo de busca sequencial em Python:
def busca_sequencial(alist, item):
    for i in range(len(alist)):
        if alist[i] == item:
            return True
    return False
A busca binária é um algoritmo otimizado em relação à busca sequencial, pois procura realizar menos iterações, evitando percorrer toda a lista para encontrar o valor desejado.
Na busca binária, os elementos da lista devem estar ordenados. Em vez de procurar o valor desejado sequencialmente, a busca binária inicia pelo exame o do item do meio da lista. Se esse elemento é o buscado, a procura encerra. Caso contrário, o item buscado é comparado com o elemento do meio: se for maior, a metade inferior da lista é deixada de ser levada em consideração para a busca; se for menor, é desconsiderada a metade superior. Isso faz com que seja descartada metade de cada lista de busca referente a cada uma das iterações.
Um exemplo de busca binária em Python:
def busca_binaria(alist, item):
    primeiro = 0
    ultimo = len(alist)-1
    while primeiro<ultimo:
        meio = (primeiro + ultimo)//2
        if alist[meio] == item:
            return True
        else:
                if item < alist[meio]:
                    ultimo = meio-1
                else:
                    primeiro = meio+1
    return False
Enunciado
Caro, aluno,
ao longo da Unidade foram abordados: a problemática do crescimento do volume de dados; conceitos e técnicas sobre algoritmos de busca, ordenação e armazenamento; bem como análise de complexidade.  Os referidos algoritmos são recursos importantes que possibilitam melhor aproveitamento da grande quantidade de informação armazenada nos repositórios de dados. Estes assuntos proporcionaram a você uma ampla visão sobre o tema, sua aplicabilidade e importância no cenário tecnológico atual. (MANZANO, J. A. N. G.; LOURENÇO, A. E.; MATOS, E. Algoritmos - Técnicas de Programação.  2. ed. São Paulo: Érica, 2015.)
Com base no material que você estudou, escreva sobre algoritmos de busca sequencial e binária, dando exemplos e buscando apresentar as diferenças.
 
Bons Estudos!