Busca Binária
Tags: algoritmos, buscabinaria, braziliandevs
Published: 2021-06-17 22:05:42

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