DEV Community

Cover image for Simplificando Binary Search 🔎
Matheus Poda
Matheus Poda

Posted on

2

Simplificando Binary Search 🔎

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


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.


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, escritor do livro Entendendo Algoritmos.

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


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;
    }

Enter fullscreen mode Exit fullscreen mode

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

        int baixo = 0;
        int alto = list.length - 1;
Enter fullscreen mode Exit fullscreen mode

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


        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;
            }
        }

Enter fullscreen mode Exit fullscreen mode
  • 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:

            if (chute == item) {
                return meio;
            }
            if (chute > item) {
                alto = meio - 1;
            } else {
                baixo = meio + 1;
            }
Enter fullscreen mode Exit fullscreen mode
  • 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


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));
    }
}

Enter fullscreen mode Exit fullscreen mode

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.


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));
    }

Enter fullscreen mode Exit fullscreen mode

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


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:

Até a próxima!

Image of Datadog

The Future of AI, LLMs, and Observability on Google Cloud

Datadog sat down with Google’s Director of AI to discuss the current and future states of AI, ML, and LLMs on Google Cloud. Discover 7 key insights for technical leaders, covering everything from upskilling teams to observability best practices

Learn More

Top comments (0)