Algoritmos de Busca¶
Objetivo¶
Ao final dessa aula você vai saber escrever algoritmos eficientes para realizar buscas em listas.
Tópicos¶
Algoritmos de Busca¶
Algoritmos de busca verificam se uma dada informação ocorre em uma sequência ou não. Por exemplo, dada uma sequência de números guardados em uma lista seq e um número x, escreva uma função que responda à pergunta: x ocorre na sequência?
Por que não usar x in seq?
Sim, em Python a gente pode usar x in seq, que resulta em True ou False caso x pertença à lista ou não. Mas nesse capítulo nosso objetivo é esclarecer como o in pode ser implementado e discutir formas eficientes de implementar busca em sequências. Um outro método útil é o index. Caso x pertença a seq, você pode utilizar seq.index(x) para descobrir o índice de x em seq.
Uma possível solução é percorrer a lista toda variando o índice i de 0 a len(seq)-1 e comparando cada elemento seq[i] com x. Caso o valor seja encontrado a função retorna True e, caso contrário, retorna False. Essa solução é conhecida como Busca Sequencial.
Exercício 1¶
Escreva um programa que leia uma sequência com N números reais e imprime a sequência eliminando os elementos repetidos. Esse exercício pode ser dividido em 2 partes:
Parte A
Escreva a função:
** Parte B**
Exercício 2¶
Quando utilizamos o algoritmo de busca sequencial para procurar um elemento de valor x em uma sequência seq, toda a sequência precisa ser varrida quando x não está presente em seq.
Para criarmos um algoritmo mais eficiente, vamos assumir que a sequência esteja em ordem alfabética, como em um dicionário. Nesse caso, ao invés de testar um elemento de cada vez sequencialmente, podemos aplicar o seguinte algoritmo:
considere o elemento M, no meio da lista.
caso x for igual a M, então a busca termina pois encontramos o valor procurado.
caso M for maior que x, então x deve estar na primeira metade da sequência. A busca deve continuar apenas nessa metade. Mas se o comprimento dessa metade for nulo, a busca deve termina e o valor não foi encontrado.
caso M for menor que x, então x deve estar na segunda metade da sequência. A busca deve continuar apenas nessa metade. mas se o comprimento dessa metade for nulo, então a busca termina e o valor não foi encontrado.
Esse algoritmo é conhecido como Busca Binária pois a cada iteração metade da sequência é eliminada da busca. Dessa forma, usando o algoritmo de busca sequencial em uma sequência com 1024 elementos, todos os 1024 elementos devem ser testados antes do algoritmo indicar que o elemento não está na lista. No caso da busca binária, o primeiro teste elimina 512 elementos, o segundo 256, o terceiro 128, e depois 64, 32, 16, 8, 4, 2, até que a lista contenha apenas 1 elemento. Dessa forma, ao invés de 1024, apenas 10 elementos (ou log(len(seq))) precisam ser testados.