sexta-feira, 26 de setembro de 2014

[Python] - Busca binária (binary search)

Olá pessoal, nesse post iremos falar sobre a busca (pesquisa) binária.

Trata-se de uma busca onde o vetor precisa está ordenado. O espaço de busca é sempre reduzido à metade, pois obtém-se o elemento do meio para que possam ser feitas as comparações com o elemento buscado.

A busca binária utiliza o paradigma de divisão e conquista onde "quebramos" um problema maior em subproblemas menores até que possamos de fato resolvê-lo.

Assista ao vídeo abaixo para entender melhor a busca binária:


Vamos pegar um exemplo bem simples, vamos supor que temos o seguinte vetor:

[1, 10, 15, 25, 30]

O elemento a ser buscado é o valor 10.

Temos dois limites: o limite inferior e o limite superior. Esses limites marcam o espaço de busca atual.

No início o nosso espaço de busca é todo o vetor.

Pega-se o elemento do meio: 15

Comparamos com o elemento que estamos procurando (10). 15 é maior do que 10, isso quer dizer que o elemento que buscamos está à esquerda do elemento do meio, por isso, podemos descartar o elemento do meio e todos aqueles que estão à sua direita (25 e 30).

Nosso espaço de busca se reduz a apenas dois elementos: 1 e 10.

Repetimos o processo pegando o elemento do meio. O nosso limite inferior é 0 e nosso limite superior é 2. O elemento do meio é a soma do limite inferior com o superior dividido por 2.

meio = (limite_inferior + limite_superior) / 2
meio = (0 + 2) / 2 = 1

vet[meio] = vet[1] = 10

Comparamos novamente o vet[meio] com o número que estamos procurando.

vet[meio] = 10 e o número que estamos procurando também é 10. O número buscado foi achado na segunda tentativa.

E se fossem milhões de números? A busca binária seria mais interessante do que uma busca linear.

Veja a implementação em Python:

Linha 3: importação do módulo random para sortear um número.

Linha 6: definição da função binary_search_ite que realiza a busca binária de forma iterativa. Apenas dois parâmetros foram necessários: o vetor e o número (num) a ser buscado.

Linha 7: inicialização de variáveis. A variável "esquerda" é para marcar o limite inferior, "direita" marca o limite superior e "tentativa" conta a quantidade de tentativas.

Linha 9: obtém o meio do vetor. O // faz uma divisão inteira.

Linha 11: se o valor do meio for igual, então retorna o número de tentativas.

Linha 13: se o valor buscado for maior que o valor do meio, então atualiza-se a variável "esquerda" (limite inferior).

Linha 15: se o valor buscado for menor que o valor do meio, então atualiza-se a variável "direita" (limite superior).

Linha 17: incrementa o número de tentativas.

Linha 20: definição da função binary_search_rec que implementa a versão recursiva da busca binária. Foram necessários quatro parâmetros: o vetor, o número a ser buscado, "esq" marca o limite inferior, "dir" marca o limite superior e "tentativa" é o contador.

Linha 21: cálculo do meio.

Linhas 23 à 27: similar a função anterior só que com chamadas recursivas.

Linha 30: teste das funções.

Linha 31: gera uma lista com 1 milhão de elementos.

Linha 32: utilização do módulo random para escolher (choice) um número inteiro.

Linhas 33 a 35: impressão dos resultados.

Quaisquer dúvidas deixem nos comentários, até a próxima.


Nenhum comentário: