PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO - Atividade 1

Prévia do material em texto

PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO
Atividade 1
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.
Resposta:
Em Ciência da Computação, um algoritmo de busca é o procedimento usado para localizar dados específicos entre uma coleção de dados.
Um algoritmo de busca sequencial, às vezes chamado de Busca Linear, é um algoritmo de busca que checa, de forma sequencial, cada elemento de uma lista até que uma correspondência seja encontrada ou então que toda a lista tenha sido percorrida.
Na busca sequencial não é necessário que os dados da lista que se deseja pesquisar estejam ordenados.
Um exemplo de um algoritmo de busca linear, na linguagem Python:
def buscaLinear(lista, n, x):
 
    for i in range(0, n):
        if (lista[i] == x):
            return i
    return -1
Já a busca binária é um algoritmo de busca utilizado em uma lista ordenada, dividindo repetidamente o intervalo de busca pela metade. A ideia da busca binária é usar a informação de que a lista está ordenada e reduzir a complexidade de tempo para O(Log n).
De forma geral, um passo a passo de uma busca binária poderia ser resumida da seguinte forma (onde x é o elemento que se deseja encontrar):
1. Compare x com o elemento do meio da lista.
2. Se x corresponder ao elemento do meio, retorna-se o índice do meio.
3. Caso contrário, se x for maior que o elemento médio, então x só pode estar na metade do subarray direito (maior) após o elemento médio. Em seguida, aplicamos o algoritmo novamente para a metade direita.
4. Caso contrário, se x for menor que o elemento do meio, então x deve estar na metade esquerda (inferior) do subarray. Então aplicamos o algoritmo para a metade esquerda.
Um exemplo de um algoritmo de busca binária, na linguagem Python:
def busca_binaria(lista, x):
    low = 0
    high = len(lista) - 1
    mid = 0
 
    while low <= high:
 
        mid = (high + low) // 2
 
        if lista[mid] < x:
            low = mid + 1
 
        elif lista[mid] > x:
            high = mid - 1
 
        else:
            return mid
 
    return -1
Algumas diferenças importantes entre algoritmos de busca sequencial e binária são:
· Na busca sequencial, os dados de entrada não precisam estar ordenados. Já na busca binária sim.
· A complexidade de tempo da busca linear é O(n). A complexidade de tempo da busca binária é O(log n).
· A busca linear executa comparações de igualdade. A busca binária realiza comparações de ordenação.
· A busca linear é menos complexa e é um processo mais lento. Já a busca binária é mais complexa e mais rápida.