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.

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:

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:

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.

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...

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.

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.

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

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

        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

        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:

            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

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.

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;
• Big O cheat sheet;

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
• LinkedIn
• Twitter
• YouTube

Até a próxima!