Busca Binária

TheNewHackers — Thu, 17 Jun 2021 22:05:42 +0000

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/built_in_binary_search.rb

https://github.com/TheNewHackers/busca-algoritmos/blob/master/binary_search/naive.rb

DEV Community: TheNewHackers

Busca Binária

"Dado um array de inteiros ordenado, descubra se o número 42 está nesse array"

Busca Binária implementada pelo Ruby

Entendendo a Busca Binária