Irei escrever sobre algoritmos e estruturas de dados em paralelo com o livro Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos de Aditya Y. Bhargava.
Estou usando o livro para aprender sobre algoritmos e estruturas de dados, e escrever sobre o que estou aprendendo, pois acredito que assim eu consiga fixar melhor o conteúdo.
Capítulo 1 — Introdução a algoritmos
Pesquisa binária
Vamos supor que você tem uma tabela de 100 id de forma ordenada, e você quer saber se o id 77 está na tabela.
Existem duas formas de fazer isso, a primeira é percorrer a tabela do início ao fim, mas isso é muito custoso, pois você precisa percorrer todos os 100 elementos da tabela. A segunda forma é usar a pesquisa binária, sendo uma forma de dividir o problema em subproblemas menores, e depois combinar as soluções desses subproblemas para obter a solução do problema original.
A pesquisa binária funciona da seguinte forma:
- Comece no meio da tabela.
- Se o id do meio for o que você está procurando, você acabou.
- Se o id do meio for maior do que o que você está procurando, repita a pesquisa na metade da tabela à esquerda.
- Se o id do meio for menor do que o que você está procurando, repita a pesquisa na metade da tabela à direita.
- Repita até que você encontre o id ou até que a tabela esteja vazia.
Um exemplo ótimo que está no livro é o seguinte:
Você está procurando uma palavra no dicionário. Nesse dicionário existem 240 mil palavras. No pior dos casos você teria que olhar todas as 240 mil palavras para encontrar a palavra que você está procurando.
De quantas etapas você precisa para encontrar a palavra que está procurando?
Se formos fazer a pesquisa simplesmente do início ao fim, precisaríamos de 240 mil etapas, o que é muito custoso.
Agora vamos usar a pesquisa binária:
A cada etapa da pesquisa binária, você está reduzindo o número de palavras que você precisa olhar pela metade.
240K → 120K → 60K → 30K → 15K → 7.5K → 3.75K → 1.875K → 938 → 469 → 235 → 118 → 59 → 30 → 15 → 8 → 4 → 2 → 1.
Nele, você precisa de 18 etapas para encontrar a palavra que você está procurando. Repare que a pesquisa binária é muito mais rápida do que a pesquisa simples.
Em uma lista de X elementos, a pesquisa binária precisa de log2(X) etapas para encontrar o elemento que você está procurando.
Logaritmos são o inverso da exponenciação.
Se você tem um número X elevado a uma potência Y, você pode tirar a potência Y do número X para obter o logaritmo de X na base Y.
102 = 100 → log10(100) = 2
103 = 1000 → log10(1000) = 3
23 = 8 → log2(8) = 3
24 = 16 → log2(16) = 4 25 = 32 → log2(32) = 5
Exemplos:
Exemplo feito em python:
def pesquisa_binaria(lista, item):
baixo = 0
alto = len(lista) - 1
while baixo <= alto:
meio = (baixo + alto) // 2
chute = lista[meio]
if chute == item:
return meio
if chute > item:
alto = meio - 1
else:
baixo = meio + 1
return None
minha_lista = [1, 3, 5, 7, 9]
print(pesquisa_binaria(minha_lista, 3)) # 1
print(pesquisa_binaria(minha_lista, -1)) # None
Esses exemplos foram retirados do livro Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos de Aditya Y. Bhargava.
Sabendo que uma das linguagens mais usadas é o JavaScript, vou fazer um exemplo em JavaScript:
function pesquisaBinaria(lista, item) {
let baixo = 0;
let alto = lista.length - 1;
while (baixo <= alto) {
let meio = Math.floor((baixo + alto) / 2);
let chute = lista[meio];
if (chute === item) {
return meio;
}
if (chute > item) {
alto = meio - 1;
} else {
baixo = meio + 1;
}
}
return null;
}
let minhaLista = [1, 3, 5, 7, 9];
console.log(pesquisaBinaria(minhaLista, 3)); // 1
console.log(pesquisaBinaria(minhaLista, -1)); // null
Vamos entender entre linhas o que esta acontecendo no código acima:
function pesquisaBinaria(lista, item) {
let baixo = 0;
let alto = lista.length - 1;
//Aqui estamos definindo as variáveis baixo e alto, que são os limites da lista que estamos procurando.
//O baixo é o primeiro elemento da lista, e o alto é o último elemento da lista.
while (baixo <= alto) {
let meio = Math.floor((baixo + alto) / 2);
let chute = lista[meio];
if (chute === item) {
return meio;
}
if (chute > item) {
alto = meio - 1;
} else {
baixo = meio + 1;
}
}
return null;
}
//No primeiro momento usamos as variáveis baixo e alto para encontrar o meio da lista.
//Depois, verificamos se o chute é igual ao item que estamos procurando.
//Se for, retornamos o meio.
//Se não for, verificamos se o chute é maior que o item que estamos procurando.
//Se for, o alto é o meio - 1. Se não for, o baixo é o meio + 1.
//Isso é feito até que o chute seja igual ao item que estamos procurando ou até que a lista esteja vazia.
Uma coisa que você deve ter notado é que a lista precisa estar ordenada para que a pesquisa binária funcione. Se a lista não estiver ordenada, você pode ordená-la primeiro e depois fazer a pesquisa binária.
Tempo de execução
Algo citado no livro é sobre o tempo de execução de um algoritmo.
Com a pesquisa binária, o tempo de execução é O(log n).
Com a pesquisa simples, o tempo de execução é O(n).
Isso gera muita economia no processamento e torna a pesquisa muito mais poderosa e eficiente
Finalização
Essa foi uma pequena documentação dos meus estudos, espero que possa ajudar mais pessoas.
Qualquer dúvida, correção ou sugestão pode deixar nos comentários.
