Pesquisas em listas com Python
Pesquisa linear ou sequencial
Depois que você ordena os valores de um vetor, a pesquisa para localizá-los fica bem menos trabalhosa. Existem vários métodos de pesquisa em vetor; para a maioria, é pré-requisito que o vetor esteja ordenado, em ordem crescente ou decrescente. Você vai conhecer os métodos de pesquisa sequencial e binária.
O método de pesquisa sequencial é o mais simples: um valor é lido e, em seguida, pesquisado em um vetor até que seja encontrado ou que o vetor termine.
Esse método é mais eficaz em vetores com valores desordenados, mas também é o método mais lento de pesquisa, pois, se não localizar o valor pesquisado, percorre todo o vetor e não somente uma parte dele, como nos outros métodos. O desempenho desse método pode melhorar se ele for aplicado em um vetor ordenado; mesmo assim, ainda será inferior aos outros métodos.
Exemplo:
Problema: Em um vetor numérico de 20 posições, crie um algoritmo para encontrar a posição exata em que está armazenado um valor indicado pelo usuário.
Criar um vetor numérico de 20 posições
vetor = [5, 7, 2, 3, 8, 1, 10, 4, 6, 9, 11, 13, 14, 12, 15, 17, 16, 19, 18, 20]
Receber o valor que o usuário deseja encontrar a posição
valor_procurado = int(input(“Digite o valor que deseja encontrar: “))
Percorrer o vetor para encontrar a posição do valor procurado
posicao = None
for i in range(len(vetor)):
if vetor[i] == valor_procurado:
posicao = i
break
Verificar se o valor foi encontrado ou não
if posicao is not None:
print("O valor", valor_procurado, "foi encontrado na posição", posicao)
else:
print("O valor", valor_procurado, "não foi encontrado no vetor")
Explicando o código:
- Na primeira linha, criamos um vetor numérico de 20 posições.
- Na segunda linha, solicitamos ao usuário que insira o valor que deseja encontrar a posição.
- Em seguida, usamos um loop
forpara percorrer o vetor e verificar se cada elemento é igual ao valor procurado. Se encontrarmos o valor, armazenamos a posição em que ele está no vetor na variávelposicaoe encerramos o loop usando o comandobreak. - Finalmente, verificamos se a variável
posicaofoi preenchida com um valor (ou seja, se o valor foi encontrado) e exibimos a mensagem apropriada para o usuário.
Pesquisa binária
Esse método é mais rápido que o sequencial, pois pesquisa um número menor de dados. A cada teste, é pesquisada somente a parte do vetor que contém valores que satisfaçam a condição da pesquisa (ser o valor maior ou menor que o número lido). Para que essa pesquisa seja feita, é imprescindível que o vetor esteja ordenado.
Exemplo:
Problema: Em um vetor numérico de 20 posições em ordem crescente, faça um algoritmo para encontrar a posição exata em que está armazenado um valor indicado pelo usuário. Represente o algoritmo em pseudocódigo.
Solucionando o problema: O método de pesquisa binária consiste basicamente em encontrar a posição central do vetor, ou a mais próxima do centro. De acordo com o valor armazenado na posição equivalente ao meio, é visto se o número armazenado é maior ou menor que o número desejado.
De acordo com o valor armazenado na posição equivalente ao meio, é visto se o número armazenado é maior ou menor que o número desejado. Dependendo da resposta, escolhe-se uma das metades e novamente divide-se ao meio. Isso é feito sucessivamente até que seja encontrado o número ou seja verificado a não existência dele no vetor.
Criar um vetor numérico de 20 posições em ordem crescente
vetor = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Receber o valor que o usuário deseja encontrar a posição de 20
valor_procurado = int(input(“Digite o valor que deseja encontrar: “))
Inicializar as variáveis de limite esquerdo e direito
- esquerdo = 0
- direito = len(vetor) - 1
Realizar a pesquisa binária
while esquerdo <= direito:
meio = (esquerdo + direito) // 2
if vetor[meio] == valor_procurado:
print("O valor", valor_procurado, "foi encontrado na posição", meio)
break
elif vetor[meio] < valor_procurado:
esquerdo = meio + 1
else:
direito = meio - 1
else:
print("O valor", valor_procurado, "não foi encontrado no vetor")
Explicando o código:
- Na primeira linha, criamos um vetor numérico de 20 posições em ordem crescente.
- Na segunda linha, solicitamos ao usuário que insira o valor que deseja encontrar a posição.
- Em seguida, inicializamos as variáveis
esquerdoedireito, que representam os índices do vetor que delimitam a área em que o valor procurado pode estar. - Então, iniciamos um loop
whileque se repete enquanto a área de busca ainda tiver tamanho. Dentro do loop, calculamos o índice do elemento do meio da área de busca usando a fórmula(esquerdo + direito) // 2. - Em seguida, comparamos o valor do elemento do meio com o valor procurado. Se forem iguais, encontramos o valor e imprimimos sua posição.
- Caso contrário, ajustamos os limites esquerdo ou direito da área de busca conforme o valor do elemento do meio ser menor ou maior do que o valor procurado.
- Se o loop terminar e não tivermos encontrado o valor procurado, imprimimos uma mensagem informando que o valor não foi encontrado no vetor.
Tipos de pesquisa com Python
Em Python, é possível fazer diversos tipos de pesquisa em listas. Abaixo, descrevo alguns dos tipos mais comuns:
- Pesquisa linear: consiste em percorrer todos os elementos da lista até encontrar o elemento desejado. Esse tipo de pesquisa é relativamente simples e pode ser implementado com um loop
for.
Exemplo:
def linear_search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
1. Pesquisa binária
Funciona apenas para listas ordenadas. A cada passo, o algoritmo divide a lista em duas partes e compara o valor procurado com o valor do elemento do meio da lista. Com base nessa comparação, o algoritmo descarta uma das metades da lista e continua a busca na metade restante. Esse tipo de pesquisa é mais eficiente que a pesquisa linear, especialmente para listas grandes, pois reduz o número de elementos a serem comparados a cada passo.
Exemplo:
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
2. Pesquisa por interpolação
Semelhante à pesquisa binária, mas utiliza uma estimativa da posição do elemento desejado com base nos valores dos elementos do início e do fim da lista. A cada passo, o algoritmo calcula uma nova estimativa da posição do elemento desejado e a utiliza para determinar em qual metade da lista continuar a busca. Esse tipo de pesquisa é mais eficiente que a pesquisa binária para listas em que os elementos estão distribuídos de forma uniforme.
Exemplo:
def interpolation_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high and arr[low] <= x <= arr[high]:
mid = low + (x - arr[low]) * (high - low) // (arr[high] - arr[low])
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
3. Pesquisa por hash
Utiliza uma função hash para mapear cada valor da lista para uma posição em uma tabela de hash. Ao procurar um valor na lista, basta aplicar a função hash ao valor procurado e verificar se o elemento correspondente na tabela de hash contém o valor procurado. Esse tipo de pesquisa é muito rápido, mas requer a definição de uma função hash adequada e pode consumir muita memória caso a lista seja grande.
Exemplo:
def hash_search(arr, x):
hash_table = {}
for i in range(len(arr)):
hash_table[arr[i]] = i
if x in hash_table:
return hash_table[x]
else:
return -1
4. Pesquisa por árvore
Envolve a construção de uma árvore de busca binária a partir dos elementos da lista. Cada nó da árvore contém um elemento e dois sub-nós, que correspondem aos elementos menores e maiores do que o elemento atual. Ao procurar um valor na lista, basta percorrer a árvore a partir da raiz, comparando o valor procurado com o valor de cada nó e escolhendo a sub-árvore adequada para continuar a busca. Esse tipo de pesquisa é útil para listas que precisam ser mantidas ordenadas e suporta várias operações além da pesquisa, como inserção e remoção de elementos.
Exemplo:
class Node:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = Node(val)
else:
self._insert(val, self.root)
def _insert(self, val, cur_node):
if val < cur_node.val:
if not cur_node.left:
cur_node.left = Node(val)
else:
self._insert(val, cur_node.left)
else:
if not cur_node.right:
cur_node.right = Node(val)
else:
self._insert(val, cur_node.right)
def search(self, val):
if not self.root:
return -1
else:
return self._search(val, self.root)
def _search(self, val, cur_node):
if not cur_node:
return -1
elif cur_node.val == val:
return val
elif val < cur_node.val:
return self._search(val, cur_node.left)
else:
return self._search(val, cur_node.right)
Exercícios com pesquisa de vetores
- Encontrar o valor máximo em uma lista.
- Encontrar o valor mínimo em uma lista
- Encontrar a média dos valores em uma lista
- Contar quantas vezes um valor aparece em uma lista
- Encontrar o índice de um valor em uma lista
Resolução dos exercícios
1. Encontrar o valor máximo
lista = [1, 5, 2, 8, 3, 9]
maximo = lista[0]
for numero in lista:
if numero > maximo:
maximo = numero
print(maximo)
2. Encontrar o valor mínimo
lista = [1, 5, 2, 8, 3, 9]
minimo = lista[0]
for numero in lista:
if numero < minimo:
minimo = numero
print(minimo)
3. Encontrar a média
lista = [1, 5, 2, 8, 3, 9]
soma = 0
for numero in lista:
soma += numero
media = soma / len(lista)
print(media)
4. Contar repetições
lista = [1, 5, 2, 8, 3, 9, 5, 5]
valor = 5
contador = 0
for numero in lista:
if numero == valor:
contador += 1
print(contador)
5. Encontrar o índice
lista = [1, 5, 2, 8, 3, 9]
valor = 8
indice = None
for i in range(len(lista)):
if lista[i] == valor:
indice = i
break
print(indice)
Referências
Xavier, Gley Fabiano Cardoso Lógica de programação E-book. Disponível em: https://bibliotecadigitalsenac.com.br/?from=busca%3FcontentInfo%3D1306%26term%3Dlogica#/legacy/epub/1306 Acesso em 11/04/2023