Introdução a algoritmos — Pesquisa binária

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:

1. Comece no meio da tabela.
2. Se o id do meio for o que você está procurando, você acabou.
3. Se o id do meio for maior do que o que você está procurando, repita a pesquisa na metade da tabela à esquerda.
4. Se o id do meio for menor do que o que você está procurando, repita a pesquisa na metade da tabela à direita.
5. 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.