Introdução

Procura de dados armazenados em diferentes estruturas de dados é uma parte crucial de praticamente todas as aplicações.

Existem muitos algoritmos diferentes disponíveis para utilizar ao pesquisar, e cada um tem diferentes implementações e depende de diferentes estruturas de dados para realizar o trabalho.

Ser capaz de escolher um algoritmo específico para uma determinada tarefa é uma habilidade chave para os desenvolvedores e pode significar a diferença entre uma aplicação rápida, confiável e estável e uma aplicação que se desmorona a partir de uma simples solicitação.

• Operadores de membros
• Pesquisa linear
• Pesquisa binária
• Pesquisa de salto
• Pesquisa de fibonacci
• Pesquisa exponencial
• Pesquisa de interpolação

Operadores de membros

Algoritmos desenvolvem-se e tornam-se optimizados ao longo do tempo como resultado da constante evolução e da necessidade de encontrar as soluções mais eficientes para os problemas subjacentes em diferentes domínios.

Um dos problemas mais comuns no domínio da Informática é pesquisar através de uma colecção e determinar se um determinado objecto está ou não presente na colecção.

A maioria das linguagens de programação tem sua própria implementação de um algoritmo básico de busca, geralmente como uma função que retorna um valor de Boolean de True ou False quando um item é encontrado em uma determinada coleção de itens.

Em Python, a maneira mais fácil de procurar por um objeto é usar Operadores de Membros – nomeados dessa forma porque eles nos permitem determinar se um determinado objeto é um membro em uma coleção.

Estes operadores podem ser usados com qualquer estrutura de dados iterável em Python, incluindo Strings, Listas e Tuples.

• in – Retorna True se o elemento dado é uma parte da estrutura.
• not in – Retorna True se o elemento dado não é uma parte da estrutura.

>>> 'apple' in True>>> 't' in 'stackabuse'True>>> 'q' in 'stackabuse'False>>> 'q' not in 'stackabuse'True

Operadores de membros é suficiente quando tudo o que precisamos fazer é encontrar se uma substring existe dentro de uma determinada String, ou determinar se duas Strings, Lists, ou Tuples se interceptam em termos dos objetos que contêm.

Na maioria dos casos precisamos da posição do item na sequência, além de determinar se ele existe ou não; os operadores de membros não atendem a este requisito.

Existem muitos algoritmos de pesquisa que não dependem dos operadores embutidos e podem ser utilizados para pesquisar valores mais rapidamente e/ou com mais eficiência. Além disso, eles podem render mais informações, como a posição do elemento na coleção, em vez de apenas serem capazes de determinar sua existência.

Pesquisa linear

Pesquisa linear é um dos algoritmos de busca mais simples, e o mais fácil de entender. Nós podemos pensar nela como uma versão ampliada da nossa própria implementação de Python’s in operador.

O algoritmo consiste em iterar sobre um array e retornar o índice da primeira ocorrência de um item uma vez encontrado:

def LinearSearch(lys, element): for i in range (len(lys)): if lys == element: return i return -1

Então se usarmos a função para calcular:

>>> print(LinearSearch(, 2))

Upon executando o código, somos saudados com:

1

Este é o índice da primeira ocorrência do item que estamos procurando – tendo em mente que os índices Python são baseados em 0.

A complexidade temporal da pesquisa linear é O(n), o que significa que o tempo de execução aumenta com o número de itens na nossa lista de entrada lys.

A busca linear não é frequentemente utilizada na prática, porque a mesma eficiência pode ser alcançada usando métodos inbuilt ou operadores existentes, e não é tão rápida ou eficiente como outros algoritmos de busca.

Pesquisa linear é um bom ajuste para quando precisamos encontrar a primeira ocorrência de um item em uma coleção não classificada porque, ao contrário da maioria dos outros algoritmos de busca, não requer que uma coleção seja classificada antes do início da busca.

Pesquisa binária

Pesquisa binária segue uma metodologia de dividir e conquistar. É mais rápido que a pesquisa linear mas requer que o array seja ordenado antes do algoritmo ser executado.

Assumindo que estamos procurando por um valor val em um array ordenado, o algoritmo compara val ao valor do elemento médio do array, que chamaremos de mid.

• Se mid for o elemento que estamos procurando (melhor caso), retornamos seu índice.
• Se não, identificamos qual o lado de mid val mais provável de ser baseado no facto de val ser menor ou maior do que mid, e descartamos o outro lado do array.
• Seguimos então recursivamente ou iterativamente os mesmos passos, escolhendo um novo valor para mid, comparando-o com val e descartando metade das combinações possíveis em cada iteração do algoritmo.

O algoritmo de busca binária pode ser escrito recursivamente ou iterativamente. A recursividade é geralmente mais lenta em Python porque requer a alocação de novos quadros de pilha.

Posto que um bom algoritmo de busca deve ser o mais rápido e preciso possível, vamos considerar a implementação iterativa da busca binária:

Se usarmos a função para calcular:

>>> BinarySearch(, 20)

Recebemos o resultado:

1

Qual é o índice do valor que estamos a procurar.

A ação que o algoritmo executa a seguir em cada iteração é uma das várias possibilidades:

• Retornar o índice do elemento atual
• Procurar pela metade esquerda do array
• Procurar pela metade direita do array

Só podemos escolher uma possibilidade por iteração, e nosso conjunto de possíveis combinações é dividido por duas em cada iteração. Isto faz com que a complexidade temporal da pesquisa binária O(log n).

Uma desvantagem da pesquisa binária é que se houver múltiplas ocorrências de um elemento no array, ele não retorna o índice do primeiro elemento, mas sim o índice do elemento mais próximo do meio:

>>> print(BinarySearch(, 4))

A execução deste código resultará no índice do elemento do meio:

1

Para comparação realizando uma busca linear no mesmo array retornaria:

0

Que é o índice do primeiro elemento. Entretanto, não podemos categoricamente dizer que a busca binária não funciona se um array contém o mesmo elemento duas vezes – ela pode funcionar como a busca linear e retornar a primeira ocorrência do elemento em alguns casos.

Se executarmos a busca binária no array por exemplo, e a busca por 4, obteríamos 3 como resultado.

A busca binária é muito comumente usada na prática porque é eficiente e rápida quando comparada à busca linear. No entanto, ela tem algumas falhas, como por exemplo a sua dependência do operador //. Existem muitos outros algoritmos de busca de dividir e conquistar que são derivados da busca binária, vamos examinar alguns desses próximos.

Jump Search

Jump Search é similar à busca binária, pois funciona em um array ordenado, e usa uma abordagem similar de dividir e conquistar para pesquisar através dela.

Pode ser classificado como uma melhoria do algoritmo de busca linear uma vez que depende da busca linear para realizar a comparação real quando se procura um valor.

Dado um array ordenado, em vez de procurar através dos elementos do array de forma incremental, procuramos em saltos. Então na nossa lista de entrada lys, se tivermos um tamanho de salto o nosso algoritmo considerará elementos na ordem lys, lys, lys, lys, e assim por diante.

A cada salto, armazenamos o valor anterior que vimos e o seu índice. Quando encontramos um conjunto de valores onde lys<elemento<lys, fazemos uma pesquisa linear com lys como o elemento mais à esquerda e lys como o elemento mais à direita no nosso conjunto de pesquisa:

Posto que este é um algoritmo complexo, vamos considerar o cálculo passo a passo da pesquisa de salto com esta entrada:

>>> print(JumpSearch(, 5))

• A pesquisa de salto determinaria primeiro o tamanho do salto através do cálculo math.sqrt(len(lys)). Como temos 9 elementos, o tamanho do salto seria √9 = 3.
• Next, calculamos o valor da variável right, que é o mínimo do comprimento do array menos 1, ou o valor de left+jump, que no nosso caso seria 0+3= 3. Como 3 é menor que 8 usamos 3 como o valor de right.
• Agora verificamos se nosso elemento de busca, 5, está entre lys e lys. Como 5 não está entre 1 e 4, passamos a.
• Próximo, fazemos os cálculos novamente e verificamos se o nosso elemento de pesquisa está entre lys e lys, onde 6 é 3+jump. Como 5 está entre 4 e 7, fazemos uma pesquisa linear nos elementos entre lys e lys e retornamos o índice do nosso elemento como:

4

A complexidade temporal da pesquisa de salto é O(√n), onde √n é o tamanho do salto, e n é o comprimento da lista, colocando a pesquisa de salto entre a pesquisa linear e os algoritmos de pesquisa binários em termos de eficiência.

A vantagem mais importante da pesquisa de salto quando comparada à pesquisa binária é que ela não depende do operador de divisão (/).

Na maioria das CPUs, usar o operador de divisão é dispendioso quando comparado com outras operações aritméticas básicas (adição, subtração e multiplicação), pois a implementação do algoritmo de divisão é iterativa.

O custo por si só é muito pequeno, mas quando o número de elementos a pesquisar é muito grande, e o número de operações de divisão que precisamos realizar aumenta, o custo pode somar de forma incremental. Portanto a busca por salto é melhor que a busca binária quando há um grande número de elementos em um sistema onde mesmo um pequeno aumento na velocidade importa.

Para tornar a busca por salto mais rápida, poderíamos usar a busca binária ou outra busca interna de salto para buscar através dos blocos, ao invés de depender da busca linear muito mais lenta.

Fibonacci Search

Fibonacci search é outro algoritmo de divisão e conquista que tem semelhanças tanto com a busca binária quanto com a busca por salto. Ele recebe seu nome porque usa números Fibonacci para calcular o tamanho do bloco ou intervalo de pesquisa em cada passo.

Números Fibonacci começam com zero e seguem o padrão 0, 1, 1, 2, 3, 5, 8, 13, 21… onde cada elemento é a adição dos dois números que imediatamente o precedem.

O algoritmo funciona com três números Fibonacci de cada vez. Vamos chamar os três números fibM, fibM_minus_1, e fibM_minus_2 onde fibM_minus_1 e fibM_minus_2 são os dois números imediatamente anteriores a fibM na sequência:

fibM = fibM_minus_1 + fibM_minus_2

Inicializamos os valores para 0,1, e 1 ou os três primeiros números na sequência de Fibonacci para evitar a obtenção de um erro de índice no caso em que a nossa matriz de pesquisa lys contém um número muito pequeno de itens.

Então escolhemos o menor número da seqüência de Fibonacci que seja maior ou igual ao número de elementos em nosso array de busca lys, como o valor de fibM, e os dois números de Fibonacci imediatamente antes dele como os valores de fibM_minus_1 e fibM_minus_2. Enquanto o array tem elementos restantes e o valor de fibM é maior que um, we:

• Compare val com o valor do bloco no intervalo até fibM_minus_2, e retorna o índice do elemento se ele corresponder.
• Se o valor for maior que o elemento que estamos observando atualmente, movemos os valores de fibM, fibM_minus_1 e fibM_minus_2 dois passos para baixo na seqüência de Fibonacci, e reinicializamos o índice para o índice do elemento.
• Se o valor for menor que o elemento que estamos observando atualmente, movemos os valores de fibM, fibM_minus_1 e fibM_minus_2 um passo para baixo na seqüência de Fibonacci.

Vejamos a implementação Python deste algoritmo:

Se usarmos a função FibonacciSearch para calcular:

>>> print(FibonacciSearch(, 6))

Vejamos o processo passo-a-passo desta pesquisa:

• Determinando o menor número de Fibonacci maior ou igual ao comprimento da lista como fibM; neste caso, o menor número de Fibonacci que atende aos nossos requisitos é 13.
• Os valores seriam atribuídos como:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • index = -1
• Próximo, verificamos o elemento lys onde 4 é o mínimo de -1+5 . Como o valor de lys é 5, que é menor que o valor que estamos procurando, movemos os números de Fibonacci um degrau abaixo na seqüência, fazendo os valores:
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • index = 4
• Nextremo, verificamos o elemento lys onde 7 é o mínimo de 4+3. Como o valor de lys é 8, que é maior que o valor que estamos procurando, movemos os números de Fibonacci dois passos para baixo na seqüência.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • index = 4
• Agora verificamos o elemento lys onde 5 é o mínimo de 4+1 . O valor de lys é 6, que é o valor que estamos procurando!

O resultado, como esperado é:

5

A complexidade de tempo para a pesquisa de Fibonacci é O(log n); o mesmo que a pesquisa binária. Isto significa que o algoritmo é mais rápido que a busca linear e a busca por salto na maioria dos casos.

Fibonacci search pode ser usado quando temos um número muito grande de elementos para pesquisar, e queremos reduzir a ineficiência associada ao uso de um algoritmo que depende do operador de divisão.

Uma vantagem adicional de usar a pesquisa Fibonacci é que ela pode acomodar matrizes de entrada que são muito grandes para serem mantidas em cache de CPU ou RAM, porque ela pesquisa através de elementos em passos crescentes, e não em um tamanho fixo.

Pesquisa exponencial

Pesquisa exponencial é outro algoritmo de pesquisa que pode ser implementado muito simplesmente em Python, em comparação com a pesquisa de salto e a pesquisa Fibonacci que são ambas um pouco complexas. Também é conhecido pelos nomes de busca galopante, dupla busca e busca Struzik.

Pesquisa exponencial depende da busca binária para realizar a comparação final de valores. O algoritmo funciona por:

• Determinando o intervalo onde o elemento que estamos procurando é provável que seja
• Usando a busca binária para o intervalo para encontrar o índice exato do item

A implementação Python do algoritmo de busca exponencial é:

Se usarmos a função para encontrar o valor de:

>>> print(ExponentialSearch(,3))

O algoritmo funciona por:

• Verificando se o primeiro elemento da lista corresponde ao valor que estamos procurando – já que lys é 1 e estamos procurando por 3, definimos o índice como 1 e continuamos.
• Vasculhando todos os elementos da lista, e enquanto o item na posição do índice é menor ou igual ao nosso valor, aumentando exponencialmente o valor de index em múltiplos de dois:
  • index = 1, lys é 2, que é inferior a 3, então o índice é multiplicado por 2 e ajustado para 2,
  • index = 2, lys é 3, que é igual a 3, então o índice é multiplicado por 2 e ajustado para 4.
  • index = 4, lys é 5, que é maior que 3; o laço é quebrado neste ponto.
• Realiza então uma pesquisa binária, cortando a lista; arr. Em Python, isso significa que a sub lista conterá todos os elementos até o 4º elemento, então estamos na verdade chamando:

>>> BinarySearch(, 3)

que retornaria:

2

Que é o índice do elemento que estamos procurando tanto na lista original, quanto na lista fatiada que passamos para o algoritmo de busca binária.

Exponencial search runs in O(log i) time, where i is the index of the item we are searching for. No seu pior caso, o tempo de complexidade é O(log n), quando o último item é o item que estamos procurando (sendo n o comprimento do array).

Pesquisa exponencial funciona melhor que a busca binária quando o elemento que estamos procurando está mais próximo do início do array. Na prática, usamos a busca exponencial porque é um dos algoritmos de busca mais eficientes para arrays sem limites ou infinitos.

Pesquisa de Interpolação

Pesquisa de Interpolação é outro algoritmo de divisão e conquista, semelhante à busca binária. Ao contrário da pesquisa binária, ela nem sempre começa a pesquisa no meio. A busca por interpolação calcula a posição provável do elemento que estamos buscando usando a fórmula:

index = low + )*(high-low) / (lys-lys)]

onde as variáveis são:

• lys – nossa matriz de entrada
• val – o elemento que estamos buscando
• index – o índice provável do elemento de busca. Isto é calculado para ser um valor maior quando val está mais próximo em valor do elemento no final do array (lys), e menor quando val está mais próximo em valor do elemento no início do array (lys)
• low – o índice inicial do array
• high – o último índice do array

O algoritmo procura calculando o valor de index:

• Se for encontrada uma correspondência (quando lys == val), o índice é retornado
• Se o valor de val for menor que lys, o valor do índice é recalculado usando a fórmula para a sub-arranjo esquerda
• Se o valor de val for maior que lys, o valor para o índice é recalculado usando a fórmula para a sub-arranjo direito

Vamos prosseguir e implementar a pesquisa de Interpolação usando Python:

Se usarmos a função para calcular:

>>> print(InterpolationSearch(, 6))

Os nossos valores iniciais seriam:

• val = 6,
• low = 0,
• high = 7,
• lys = 1,
• lys = 8,
• index = 0 + = 5

Desde que lys seja 6, que é o valor que estamos procurando, paramos de executar e retornamos o resultado:

5

Se tivermos um grande número de elementos, e nosso índice não puder ser computado em uma iteração, continuamos a recalcular valores para índice após ajustar os valores de alto e baixo em nossa fórmula.

A complexidade temporal da pesquisa de interpolação é O(log log n) quando os valores são uniformemente distribuídos. Se os valores não são distribuídos uniformemente, a pior complexidade de tempo é O(n), o mesmo que pesquisa linear.

A pesquisa de interpolação funciona melhor em arrays ordenados e distribuídos uniformemente. Enquanto a busca binária começa no meio e sempre se divide em duas, a busca por interpolação calcula a posição provável do elemento e verifica o índice, tornando mais provável encontrar o elemento em um número menor de iterações.

Por que usar Python para busca?

Python é altamente legível e eficiente quando comparado com linguagens de programação mais antigas como Java, Fortran, C, C++ etc. Uma vantagem chave do uso do Python para implementar algoritmos de pesquisa é que você não precisa se preocupar com o lançamento ou digitação explícita.

Em Python, a maioria dos algoritmos de pesquisa que discutimos funcionarão tão bem quanto se estivermos pesquisando por uma String. Tenha em mente que temos que fazer alterações no código para algoritmos que usam o elemento de busca para cálculos numéricos, como o algoritmo de busca de interpolação.

Python também é um bom lugar para começar se você quiser comparar a performance de diferentes algoritmos de busca para o seu conjunto de dados; construir um protótipo em Python é mais fácil e rápido porque você pode fazer mais com menos linhas de código.

Para comparar a performance dos nossos algoritmos de busca implementados com um conjunto de dados, podemos usar a biblioteca de tempo em Python:

import timestart = time.time()# call the function hereend = time.time()print(start-end)

Conclusion

Existem muitas maneiras possíveis de procurar por um elemento dentro de uma coleção. Neste artigo, tentamos discutir alguns algoritmos de pesquisa e suas implementações em Python.

Selecionar qual algoritmo usar é baseado nos dados que você tem que pesquisar; seu array de entrada, que chamamos de lys em todas as nossas implementações.

• Se você quiser pesquisar através de um array não ordenado ou para encontrar a primeira ocorrência de uma variável de pesquisa, a melhor opção é a pesquisa linear.
• Se você quiser pesquisar através de um array ordenado, há muitas opções das quais o método mais simples e rápido é a pesquisa binária.
• Se você tem um array ordenado que você quer pesquisar sem usar o operador de divisão, você pode usar tanto a pesquisa por salto quanto a pesquisa por Fibonacci.
• Se você sabe que o elemento que você está pesquisando está provavelmente mais próximo do início do array, você pode usar a pesquisa exponencial.
• Se seu array ordenado também estiver uniformemente distribuído, o algoritmo de busca mais rápido e eficiente para usar seria a busca por interpolação.

Se você não tem certeza de qual algoritmo usar com um array ordenado, apenas tente cada um deles junto com a biblioteca de tempo do Python e escolha o que tem melhor desempenho com seu conjunto de dados.