A Busca Binária (Binary Search) é um dos algoritmos de busca mais fáceis de implementar e entender na minha opinião.
Antes de iniciarmos a explicação, vamos ver o seguinte problema:
"Dado um array de inteiros ordenado, descubra se o número 42 está nesse array"
O problema parece extremamente simples a primeira vista, e logo já pensamos em uma solução em O(N) - no pior caso. Ou seja percorrer o array do inicio até encontrar o número 42, ou chegar ao fim do array.
Por exemplo esse código em Ruby:
def naive_solution(arr)
for elem in arr
return true if elem == 42
end
false
end
Certo, mas está faltando algo nesse exercício... Qual é o tamanho desse array? Em outras palavras, qual é o valor máximo de N?
Segue abaixo o benchmark para entendermos até onde nossa solução é viável:
user system total real
N = 10^3 0.000041 0.000002 0.000043 ( 0.000038)
N = 10^4 0.000356 0.000015 0.000371 ( 0.000370)
N = 10^5 0.003486 0.000000 0.003486 ( 0.003486)
N = 10^6 0.038462 0.000000 0.038462 ( 0.038473)
N = 10^7 0.352321 0.000000 0.352321 ( 0.352354)
N = 10^8 3.532989 0.000000 3.532989 ( 3.533004)
Podemos ver que a partir de N = 10^8, nosso código já começa a apresentar problemas de desempenho!
Busca Binária implementada pelo Ruby
Antes mesmo de explicar como a Busca Binária funciona, veja o código e o benchmark dele logo abaixo:
def built_in_binary_search(arr)
!arr.bsearch { |elem| 42 - elem }.nil?
end
N = 10^3 0.000026 0.000001 0.000027 ( 0.000006)
N = 10^4 0.000019 0.000001 0.000020 ( 0.000020)
N = 10^5 0.000015 0.000001 0.000016 ( 0.000003)
N = 10^6 0.000028 0.000001 0.000029 ( 0.000030)
N = 10^7 0.000004 0.000000 0.000004 ( 0.000004)
N = 10^8 0.000004 0.000000 0.000004 ( 0.000005)
Isso mesmo, para N = 10^8, nosso código levou 0,000005 segundos para resolver o problema!
Entendendo a Busca Binária
Na busca binária sempre teremos um array ordernado, pois só através da pré-ordenação que conseguiremos fazer otimizações, de modo que passaremos a encontrar um elemento no array em O(logN).
A primeira etapa é encontrar o inicio do array atual, o fim e o meio desse array. Aqui chamaremos o inicio de L, o fim de R e o meio de MID.
Utilizaremos o seguinte array para o exemplo:
[1, 9, 15, 17, 23, 42, 80]
^ ^ ^
L MID R
Nessa primeira etapa teremos L = 0, R = 6 e MID = (L+R)/2 = 3.
Em MID teremos o valor 17, que é menor que o número procurado (42). Então como o array está ordenado, sabemos que o elemento está do lado direito, e que tudo antes de MID pode ser ignorado!
Assim partimos para a segunda etapa, onde atualizamos os valores das variáveis.
Agora L = MID (3), R continua 6, e MID = (L+R)/2 = 4
[1, 9, 15, 17, 23, 42, 80]
^ ^ ^
L MID R
Novamente o valor em MID é menor que 42, pois ele é igual a 23.
Assim partiremos para atualização das variáveis novamente.
L = MID (4), R continua 6 e MID = (L+R)/2 = 5
[1, 9, 15, 17, 23, 42, 80]
^ ^ ^
L MID R
Como o valor em MID é 42, então finalizamos nosso algoritmo!
Veja que gastamos 3 iterações para achar o número 42, e em uma busca sequencial (similar a naive_solution) gastaríamos 6 iterações! Ou seja, 2 VEZES MAIS RÁPIDO!
Abaixo segue os links dos arquivos utilizados para o benchmark:
https://github.com/TheNewHackers/busca-algoritmos/blob/master/binary_search/binary_search.rb
https://github.com/TheNewHackers/busca-algoritmos/blob/master/binary_search/naive.rb
Top comments (0)