Simplificando Binary Search 🔎
Tags: algorithms, java, beginners, programming
Published: 2023-06-29 18:57:31

Nessa série de posts que escrevo, vou falar sobre algoritmos mais utilizados para determinadas tarefas.

A ideia é sempre seguir o seguinte objetivo:
1. Demonstrar o problema que ele soluciona;
2. Demonstrar como ele soluciona;
3. Mostrar o código;
4. Mostrar algo já pronto;
5. Finalizar com uma ou mais perguntas de entrevistas, como desafio.

No post de hoje, iremos abordar **binary search**.

No final vou estar deixando uma pergunta que é muito encontrada em entrevistas técnicas, não vou dar a resposta de cara, vou adicionar ela aqui após uma semana, então tente responder e deixar nos comentários.

---

## Problema 

Imagine o seguinte cenário, em uma lista de números com 11 inteiros, podemos exibir como a matriz a baixo.

| Posição | Número inteiro |
| ----------- | ----------- |
| 0 | 1 |
| 1 | 5 |
| 2 | 8 |
| 3 | 10 |
| 4 | 12 |
| 5 | 16 |
| 6 | 19 |
| 7 | 24 |
| 8 | 26 |
| 9 | 46 |
| 10 | 84|

Precisamos criar um algoritmo que irá pesquisar pelo número inteiro e retornar sua posição, mas como podemos fazer isso?

Bom podemos aplicar uma **simple search** (pesquisa simples), que vai ser um looping varrendo de um a um, percorrendo cada posição da lista até encontrar o número que deseja. 

Em termos de Big O, que resumidamente, seria uma função de medirmos o tempo de processamento dos nossos algoritmo (caso tenha mais interesse em saber a fundo, vou deixar um artigo excencial nas referências), ao pensar nessa solução temos O(n), que chamamos de função linear.

Significa que o tempo de execução é igual ao tamanho da estrutura de dados, no caso como temos uma matriz de 11 elementos, temos que O(11), ele irá percorrer a lista e nos entregar o resultado em até 11 passos.

Mas existe uma forma de conseguirmos diminuir este tempo, usando a **binary search** (pesquisa binária), para não aprofundar muito em Big O, ela é considerada O(log2 n), que significa, **um ótimo tempo**. 

> O log2 n, significa que é log na base 2.

Podemos ver pelo gráfico a baixo:


![gráfico big o](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sooxz85q5lkr993s470a.png)

---

## O que é a binary search?

O algoritmo funciona da seguinte forma, ele cortará ao meio uma determinada lista, verificando se o item que está no meio é o que estamos procurando, caso não seja, irá condicionar se o item é maior ou menor que o do meio, conseguindo cortar a parte maior ou menor da lista e vai repetindo o processo até encontrar a posição do item que queremos.

É importante colocar aqui um **aviso importante**, não é possível usar essa forma de pesquisa, caso a lista que você está usando não esteja ordenada, pois o resultado desse algoritmos, retorna a posição do item, se tivesse dois ou mais itens iguais, ele iria ignorar e retornar o primeiro que encontrar.

Voltando ao cenário da nossa lista de números inteiros, desejamos encontrar o número 24 lista, primeiro iremos encontrar o meio:

| Posição | Número inteiro |
| ----------- | ----------- |
| 0 | 1 |
| 1 | 5 |
| 2 | 8 |
| 3 | 10 |
| 4 | 12 |
| 5 | 16 (**meio**)|
| 6 | 19 |
| 7 | 24 |
| 8 | 26 |
| 9 | 46 |
| 10 | 84|

O meio é o 16, a lista está ordenada em ordem crescente, 16 é maior ou igual a 24? Não, logo é menor que 24, cortamos a fatia de números menores na lista.

| Posição | Nome do Contato |
| ----------- | ----------- |
| 6 | 19 |
| 7 | 24 |
| 8 | 26 (**meio**)|
| 9 | 46 |
| 10 | 84|

O meio é 26, novamente entra na condicional, 26 é maior ou igual a 24? Sim! Então iremos arrancar a fatia com números maiores, sobrando...

| Posição | Nome do Contato |
| ----------- | ----------- |
| 6 | 19 |
| 7 | 24 |

O meio agora é 1.5, mas como a posição é inteira, iremos arredondar para 1 (como normalmente as linguagens de programação fazem). Logo temos 19, esse número é maior que 24? Não, então cortamos.

| Posição | Nome do Contato |
| ----------- | ----------- |
| 7 | 24 |

Por fim sobrou nosso número! Como retorno iremos receber **7**, que é a posição da lista que se encontra o número 24. 

Viu como ficou mais rápido? Encontramos o valor em 3 passos, sendo que se fossemos pela simple search levariamos até 11 passos.

A fórmula para você descobrir quantos passos levaria é bem simples.

| Pesquisa | Fórmula |
| ----------- | ----------- |
| Simple Search | n |
| Binary Search | log 2 n (log de base 2)|

Exemplo:

Suponha que você tenha uma lista com 128 números e esteja fazendo uma pesquisa simples e binária. Qual seria o número máximo de etapas que você levaria para encontrar o número desejado?

**Pesquisa simples O(n) = O(128), logo 128 passos**
**Pesquisa binária O(log2 n) = O(7)**

Para realizar o cálculo de log, pode usar uma calculadora científica, ou usar um site como [este](https://miniwebtool.com/br/log-base-2-calculator/).

---

## O código do algoritmo 

Beleza, entendemos a teoria, agora vamos colocar na prática e desenvolver um código que seja capaz de funcionar como explicado.

> Irei estar utilizando Java, mas o belo dos algoritmos é que ela pode ser escrita em qualquer linguagem, dê uma olhada no repositório do [Aditya Bhargava](https://github.com/egonSchiele/grokking_algorithms/tree/master/01_introduction_to_algorithms), escritor do livro _Entendendo Algoritmos_.

Vou estar colocando o código inteiro e vamos quebrar em etapas:

```java

private static Integer binarySearch(int[] list, int item) {
        int baixo = 0;
        int alto = list.length - 1;

        while (baixo <= alto) {
            int meio = (baixo + alto) / 2;
            int chute = list[meio];
            if (chute == item) {
                return meio;
            }
            if (chute > item) {
                alto = meio - 1;
            } else {
                baixo = meio + 1;
            }
        }
        return null;
    }

```

Parte 1: Definindo o máximo e mínimo da lista

```java
        int baixo = 0;
        int alto = list.length - 1;
```

Aqui praticamente estamos adotando o primeiro valor máximo e mínimo da lista, começando com 0, e como as matrizes e vetores começam com 0, nós fazemos o tamanho da lista -1 para encontrar o máximo.

Parte 2: O algoritmo

```java

        while (baixo <= alto) {
            int meio = (baixo + alto) / 2;
            int chute = list[meio];
            if (chute == item) {
                return meio;
            }
            if (chute > item) {
                alto = meio - 1;
            } else {
                baixo = meio + 1;
            }
        }

```

* O looping será executado até que o alto fique igual ou menor que baixo;

Definimos o valor que representa o meio.
`int meio = (baixo + alto) / 2;`

E o valor do chute.
`int chute = list[meio];`

Tendo isso em mente, vamos agora verificar a condicional que expliquei na teoria:

```java
            if (chute == item) {
                return meio;
            }
            if (chute > item) {
                alto = meio - 1;
            } else {
                baixo = meio + 1;
            }
```

* Se o chute for igual ao item, retornamos a posição do meio.
* Se o chute for maior que o item, iremos alterar o valor do tamanho máximo da lista, para que cortemos os valores maiores que o meio.
* Se o chute for menor que o item, iremos alterar o valor do tamanho mínimo da lista, para que cortemos os valores menores que o meio.

Assim no final iremos conseguir, caso exista o número na lista, encontrar sua posição, caso contrário, retorna nulo.

**Código para você brincar no seu compilador**

```java 

import java.util.Arrays;

public class BinarySearch {


    private static Integer binarySearch(int[] list, int item) {
        int baixo = 0;
        int alto = list.length - 1;

        while (baixo <= alto) {
            int meio = (baixo + alto) / 2;
            int chute = list[meio];
            if (chute == item) {
                return meio;
            }
            if (chute > item) {
                alto = meio - 1;
            } else {
                baixo = meio + 1;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        int[] minhaLista = {1,5,8,10,12,16,19,24,26,46,84};
        System.out.println(binarySearch(minhaLista, 24));
        System.out.println(binarySearch(minhaLista, -1));
    }
}

```
## Simplificações do Colections do Java

Obviamente no mercado, se você precisar de uma binary search, a Colections do Java, já tem esse algoritmo pronto, basta usar da seguinte forma.

```java

public static void main(String[] args) {
        List<Integer> listaInteiros = Arrays.asList(1,5,8,10,12,16,19,24,26,46,84);
        int[] minhaLista = {1,5,8,10,12,16,19,24,26,46,84};
        int item = 24;
        System.out.println(Collections.binarySearch(listaInteiros, item));
        System.out.println(Arrays.binarySearch(minhaLista, item));
    }

```

## Pergunta de entrevista

Pergunta: Dado uma lista ordenado em ordem descrescente de números inteiros, escreva um código que encontre o elemento da lista, considerando o fator de tempo, como O(log2 n).

Exemplo:
**INPUT: Encontre o valor 8 em {42,36,29,25,14,8,3,1}**  
**OUTPUT: 5**

---

## Resposta da pergunta

> A resposta será liberada no dia 06/07/23, a ideia é que você tente resolver e disponibilize sua ideia e código nos comentários (código pode subir no github e postar aqui, mas explique o que você pensou).

--- 
## Referências

* Entendendo Algoritmos: Um guia ilustrado, por Aditya Y. Bhargava;
* Algoritmos, de José Augusto e Jaya Figueireido;
* Cracking the Coding Interview, de Gayle Laakmann;

---
## Links úteis

* [Big O](https://www.youtube.com/watch?v=Z0bH0cMY0E8);
* [Big O cheat sheet](https://www.bigocheatsheet.com/);

--- 

## Me acompanhe em minhas redes sociais. 

Obrigado pelo seu tempo!

Compartilhem com seus colegas de estudo/trabalho.
Me chama nas redes sociais a baixo para trocarmos uma ideia e tirar dúvidas:
* [GitHub](https://github.com/matskira)
* [LinkedIn](https://www.linkedin.com/in/matheuspoda/)
* [Twitter](https://twitter.com/devmpoda)
* [YouTube](https://www.youtube.com/@devmpoda/videos)

Até a próxima!