Simplificando Binary Search 🔥🔎
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:
- Demonstrar o problema que ele soluciona;
- Demonstrar como ele soluciona;
- Mostrar o código;
- Mostrar algo já pronto;
- 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:
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;
}
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
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!
