Técnicas de Busca

Motivação

• Quando a quantidade de dados aumenta e trabalhamos com coleções de dados em memória, começa a surgir a necessidade de fazer buscas sobre os dados
• Por exemplo, suponha que tenhamos lido os dados diários de várias estações meteorológicas do país a partir de um arquivo. Suponha ainda que estes dados foram lidos e colocados em listas: uma com os nomes das cidades, outra com a temperatura máxima diária e outra com a temperatura mínima diária. Suponha que queiramos saber:
• Se há alguma cidade com temperatura máxima diária acima de 40ºC;
• Quantas cidades no país estão com temperatura mínima diária abaixo de 15ºC;
• Quais as cidades com temperatura acima de 35ºC.

Padrões típicos de busca em coleções

• Existência: verificar se existe ou não na lista um elemento correspondendo a uma certa regra.
• Por exemplo, verificar se há alguma cidade com temperatura máxima diária acima de 40ºC. A resposta será True ou False.
• Quantidade: verificar quantos elementos correspondendo a uma certa regra existem em uma lista.
• Por exemplo, verificar quantas cidades no país estão com temperatura mínima diária abaixo de 15ºC.
• Elementos: verificar quais elementos correspondendo a uma certa regra estão em uma lista.
• Por exemplo, verificar quais as cidades com temperatura máxima acima de 35ºC. A resposta será uma lista de elementos (cidades, no caso).

Busca sequencial em uma lista

• Todos os três padrões anteriores podem ser resolvidos com buscas sequenciais sobre listas.
• Buscas sequenciais percorrem a lista em ordem:
• Existência: Há alguma cidade com temperatura máxima diária acima de 40ºC?
• Basta percorrer a lista até encontrar o primeiro elemento
• Quantidade: Quantas cidades no país estão com temperatura mínima diária abaixo de 15ºC?
• Percorrer a lista completa, incrementando contador a cada match
• Elementos: Quais as cidades com temperatura máxima acima de 35ºC?
• Percorrer a lista completa, adicionando em nova lista os nomes das cidades nos índices das temperaturas acima de 35ºC

Lendo as listas a partir de um arquivo

def lerDadosString(nomeArquivo):

with open(nomeArquivo) as arquivo:

lista = []

for linha in arquivo:

str = linha[:-1].strip()

lista.append(str)

return lista

def lerDadosFloat(nomeArquivo):

with open(nomeArquivo) as arquivo:

lista = []

for linha in arquivo:

valor = float(linha)

lista.append(valor)

return lista

# programa principal

cidades = lerDadosString('cidades.txt')

maximas = lerDadosFloat('maximas.txt')

minimas = lerDadosFloat('minimas.txt')

​

​

Busca por Existência: Há alguma cidade com temperatura máxima diária acima dos 40ºC?

...

cidades = lerDadosString('cidades.txt')

maximas = lerDadosFloat('maximas.txt')

minimas = lerDadosFloat('minimas.txt')

​

for temperatura in maximas:

if temperatura > 40.0:

print('Uma cidade passou dos 40 graus')

break

else:

print('Nenhuma cidade passou dos 40 graus')

Busca por Quantidade: Quantas cidades no país estão com temperatura mínima diária abaixo de 15ºC?

...

cidades = lerDadosString('cidades.txt')

maximas = lerDadosFloat('maximas.txt')

minimas = lerDadosFloat('minimas.txt')

​

contador = 0

for temperatura in minimas:

if temperatura < 15.0:

contador += 1

print('Número de cidades abaixo dos 15 graus: %d' \

% contador)

Busca por Elementos: Quais as cidades com temperatura máxima acima de 35ºC?

...

cidades = lerDadosString('cidades.txt')

maximas = lerDadosFloat('maximas.txt')

minimas = lerDadosFloat('minimas.txt')

​

contador = 0

cidadesQuentes = []

for i in range(len(maximas)):

temperatura = maximas[i]

if temperatura > 35.0:

# relacionando cidades e máximas pelo índice i

cidade = cidades[i]

cidadesQuentes.append(cidade)

print('Estas foram as cidades com temperatura')

print('máxima acima dos 35 graus:\n')

for cidade in cidadesQuentes:

print(cidade)

Ordem de complexidade da busca

• Existência: verificar se existe ou não na lista um elemento correspondendo a uma certa regra.
• No melhor caso, encontra o elemento na primeira posição: O(1)
• No pior caso, encontra o elemento na última posição: O(n)
• No caso médio, supondo que há m elementos que respeitam a regra e n elementos na lista: O(n/m)
• Quantidade: verificar quantos elementos correspondendo a uma certa regra existem em uma lista.
• Sempre é preciso verificar os n elementos: O(n)
• Elementos: verificar quais elementos correspondendo a uma certa regra estão em uma lista.
• Sempre é preciso verificar os n elementos: O(n)

Busca binária em uma lista

• Acelera o processo de uma busca por Existência
• Para saber se há algum elemento que corresponde à regra da busca: retorna True ou False
• Para encontrar a primeira ocorrência do elemento que corresponde à regra da busca: retorna normalmente o índice do elemento (ou o próprio elemento, em alguns casos)
• Para fazer uma busca binária, é necessário que a lista esteja ordenada previamente de acordo com algum critério (numérico ou lexicográfico)

Como funciona a busca binária?

• Procure no centro da lista
• Se o elemento procurado for menor que o do centro, procure à esquerda do centro
• Se o elemento procurado for maior que o do centro, procure à direita do centro
• Por exemplo, busque o número 60 na lista
• A lista tem 9 elementos
• O centro da lista é a posição (0+8)//2 = 4
• Achou o elemento no centro da lista: melhor caso

• A lista tem 9 elementos
• O centro da lista é a posição (0+8)//2 = 4
• Não achou o elemento na posição 4
• O elemento procurado é maior que o elemento na posição 4: procure à direita, nas posições de 5 a 8
• A nova lista tem 4 elementos
• O centro da lista é a posição (5+8)//2 = 6
• Não achou o elemento na posição 6
• O elemento procurado é maior que o elemento na posição 6: procure à direita, nas posições de 7 a 8
• A nova lista tem 2 elementos
• O centro da lista é a posição (7+8)//2 = 7
• Achou o elemento na posição 7

E se a busca fosse pelo número 150?

Função Iterativa de Busca Binária

​

def buscaBinaria(lista, chave):

inicio = 0

final = len(lista)-1

while inicio <= final:

meio = (inicio + final)//2;

if lista[meio] == chave:

# achou a chave no meio

return meio

elif lista[meio] < chave:

# procure à direita

inicio = meio + 1

else:

# procure à esquerda

final = meio – 1

# se não achou retorne o índice -1

return -1

Busca Binária Recursiva

• busca_binária([7, 13, 20, 35, 60, 90, 110, 150, 200], 35)
• 60 é o elemento central, ele é maior que o elemento buscado
• Repete-se a busca na parte inicial da lista
• busca_binária([7, 13, 20, 35], 35)
• 13 é o elemento central, ele é menor que o elemento buscado
• Repete-se a busca na parte final da lista
• busca_binária([20, 35], 35)
• 20 é o elemento central, ele é menor que o elemento buscado
• Repete-se a busca na parte final da lista
• busca_binária([35], 35)
• 35 é o elemento central
• Elemento encontrado!

Função Recursiva de Busca Binária para verificar a Existência da chave

​

def buscaBinaria(lista, chave):

meio = len(lista)//2

if not lista:

return False

elif lista[meio] == chave:

return True

elif lista[meio] > chave:

# procure à esquerda

return buscaBinaria(lista[:meio],chave)

else:

# procure à direita

return buscaBinaria(lista[meio+1:],chave)

Busca binária Recursiva para localizar a Posição da chave

• Não se pode retornar a posição do elemento na última chamada recursiva, pois a cada chamada recursiva, a lista se reduz em tamanho
• Para evitar este problema, quando fizermos a busca na parte final da lista, somamos ao índice do elemento o número de elementos que foram removidos da parte inicial da lista
• O número de elementos removidos é igual ao valor da posição do centro
• Além disso, quando o elemento não é encontrado na sublista, a função deve retornar -1 (ou None, se for o objeto a ser retornado)

Função Recursiva de Busca Binária para localizar a Posição da chave

​

def buscaBinaria(lista, chave):

meio = len(lista)//2

if not lista:

return -1

elif lista[meio] == chave:

return meio

elif lista[meio] > chave:

# procure à esquerda

return buscaBinaria(lista[:meio],chave)

else:

# procure à direita

resultado = buscaBinaria(lista[meio+1:],chave)

if resultado == -1:

return resultado

else:

return resultado + meio + 1

Complexidade

Busca Sequencial versus Busca Binária