Introdução aos algoritmos de busca em Python

Um algoritmos de busca em vetor é um algoritmo para procurar a presença ou não de determinado valor em uma sequência de dados em memória (em um vetor). Deve-se destacar que a realização de busca é provavelmente o algoritmo mais empregado na prática, por exemplo, sempre que acessa um sistema com usuário e senha será necessário buscar pelo seu usuário e depois vefificar se a senha está correta.

Podemos separar a classe dos algoritmos busca em duas grandes categoria, aqueles cujos elementos estão ordenados e aqueles não ordenados. Na segunda categoria o tempo de busca é diretamente proporcional ao número de elementos, se existem N elementos, no pior caso (e.g. quando o elemento procurado não existe no vetor) serão realizadas N comparações (ou 2*N se algoritmo implementado não usar sentinela - vide seção 1.1). Por outro lado, se os dados estiverem ordenados, é possível implementar um algoritmo tremendamente mais rápido, o algoritmo de busca binária, que no pior caso realiza apenas log₂(N) comparações.

Fig. 1. Ilustração da busca por x em um vetor não ordenado Vet em memória.

1. Busca em vetor não ordenado

Um primeiro algoritmo para buscar um dado elemento em um vetor não ordenado pode ser obtido usando um enumerador (contador) iniciado com o primeiro elemento do vetor, se for igual ao buscado devolve esse índice, senão examine o próximo a assim por diante, como ilustrado na figura 2 e detalhado no código 1.

Vale destacar que é mais eficiente devolver o índice (digamos ind) e não o valor (que coincidiria com o procurado, digamos x), pois, como esse é sempre maior ou igual ao zero (0), poderíamos adotar o -1 como indicador de não ocorrência, além de ser fácil a conferência (bastaria examinar novamente que x == vet[ind]).

Fig. 2. Ilustração do fluxo de execução de uma função para buscar por x em um vetor não ordenado v.

Note que nesse primeiro algoritmo, o tempo de execução é basicamente determinado pelas duas comparações, a primeira que verifica se ainda não chegamos ao final do vetor (i<N) e a segunda verificando se o elemento atual é igual ao procurado (x == v[i]).

# Funcao para buscar pelo elemento x em vetor nao ordenado
# Devolve: -1 se x nao existente em v; i se x=v[i] (em caso de empate devolve o menor i)
def busca (v, x, N) :
  i = 0;
  while (i < N) : # Primeira comparacao: ainda existem elementos em "v"
    if (x == v[i]) : # elemento encontrado devolve sua posicao (indice)
      return i;
    i++; # tenta com o proximo
  return -1; # elemento NAO existe em "v"!
  # def busca(.)

Cód. 1. Código ilustrando a busca não informada com duas comparações por passo.

Desse modo, o algoritmo acima realiza exatamente 2*N comparações no pior caso de busca (quando o elemento não existe no vetor). Dizemos que esse algoritmo tem complexidade (de pior caso e média) da ordem de N, ou usando a simbologia O(N). O(n) significa que o tempo de execução, contabilizado em termos de comparações, é limitado por uma função linear no tamanho dos dados (n).

1.1 Busca com sentinela

Uma ideia simples, mas que praticamente reduz pela metade o tempo de busca, é usar o conceito de um sentinela, uma cópia do elemento procurado artificialmente inserida após a última posição usada no vetor. Assim, se o vetor tiver N elementos (desde 0 até N-1), então faz-se Vet[N] = x e com isso podemos eliminar metade das comparações, como indicado no código 2.

# Funcao para buscar o elemento x em vetor nao ordenado usando sentinela
# Devolve: -1 se x nao existente em v; i se x=v[i] (em caso de empate devolve o menor i)
def sentinela (v, x, N) : # poderia-se dispensar N computando-o na funcao: N = len(v)
  i = 0;
  v.append(x); # cria v[N] com x
  while (x != v[i]) : # No pior caso, para no sentineta, significando que nao existe "x" em "v"
    i++;
  v = v[:N-1]; # IMPORTANTE: remover a sentinela
  if (i < N) : # encontrou em outra posicao anterior ao sentinela, logo existe em "v[i]"!
    return i;
  return -1; # se encontrou na posicao N, entao e' o sentinela, logo nao existe em "v[.]"
  # int sentinela(.)

Cód. 2. Busca mais eficiente: com sentinela.

Note que, com a inserção do sentinela, basta usar como controle do laço a detecção do elemento buscado x, uma vez que x foi inserido após o último elemento do vetor (evitando o desagradável erro de laço infinito).

Em termos de complexidade de execução o comportamento da busca com sentinela é igual ao da busca menos eficiente, ambas da ordem de N (O(N)), mas na prática a busca com sentinela é mais rápida.

2. Busca em vetor ordenado: busca binária

Como discutido na seção 1, as buscas em vetor não ordenado tem complexidade O(N), mas se o vetor estiver ordenado pode-se construir um algoritmo significativamente mais efeciente, a busca binária, cuja complexidade de execução é de apenas log₂(N). Por exemplo, se N=4.294.967.296 (pouco mais que 4 milhões e meio de elementos), enquanto os algoritmos da seção 1 teriam que realizar em média mais de 2 milhões de comparações, a busca binária precisaria, no pior caso, realizar apenas 32 comparações!
Justificando: como N = 4.294.967.296 = 2³², então log₂(4.294.967.296)=log₂(2³²) = 32*log₂(2) = 32.

Se pensarmos em uma situação típica, como acessos à conta bancária, a quantidade de operações de busca certamente é muito maior que o número de vezes que a base de clientes é alterada (removendo ou inserindo alguém). Desse modo, comparativamente com o números de buscas realizadas, a base de dados pouco muda, então vale a pena ordenar os dados (assunto de outro texto) e a partir dai usar o algoritmo de busca binária.

A ideia da busca binária é, sendo esq=0 e dir=N-1 os extremos do vetor, examinar o elemento do meio (meio = (esq+dir)/2),

1. se v[meio]<x, então pode-se ignorar todos os elementos entre v[0] e v[meio], ou seja, repete-se o processo agora com extremos meio+1 e N-1; por outro lado,
2. se v[meio]>x, então pode-se ignorar todos os elementos entre v[meio] e v[N-1], ou seja, repete-se o processo agora com extremos 0 e meio-1; por fim,
3. se v[meio]==x, então encontramos o elemento, finalize o processo devolvendo meio.

Fig. 3. Ilustração da busca binária: (a) de elemento existente; (b) de elemento inexistente em v.

Abaixo apresentamos o código completo da função busca_binaria implementando a busca binária (de modo iterativo, a implementação de modo recursiva fica ainda mais simples).

# Funcao para buscar pelo elemento x em vetor ordenado crescente
# Devolve: -1 se x nao existente em v; i se x=v[i] (em caso de empate devolve o primeiro encontrado)
def busca_binaria (v, x, N) : # poderia-se dispensar N computando-o na funcao: N = len(v)
  esq = 0; dir = N-1;
  while (esq <= dir) : # No pior caso para no sentineta => nao existe "x" em "v"
    meio = (esq + dir) // 2; # Lembre-se que e' a divisao inteira, e.g., (2+3)//2 = 2 
    if (v[meio] < x) : # ignorar v[0] a v[meio]
      esq = meio+1;
    elif (v[meio] > x) : # ignorar v[meio] a v[dir]
      dir = meio-1;
    else : # v[meio] == x => encontrei!
      return meio;
  return -1; # NAO encontrei...

Cód. 3. Busca binária que, no máximo, precisa realizar O(log₂(N) operações.

Leônidas de Oliveira Brandão
http://line.ime.usp.br