Entendendo algoritmos - Pesquisa binária

Entendendo problemas de busca

Vamos supor que você esteja procurando o nome de uma pessoa em uma agenda ordenada em ordem alfabética. O nome da pessoa que deseja encontrar começa com a letra "K”, sendo assim, é comum começar a busca pelo meio da lista, certo? Dessa forma, a busca seria mais rápida. Podemos também dar o exemplo do próprio Facebook, quando você faz o login, ele precisa buscar seu nome no banco de dados. Nesse caso, a busca também começa pelo meio caso seu nome comece com a letra “M”, por exemplo.

Esses são exemplos de problemas de busca que podem ser resolvidos usando o algoritmo de pesquisa binária.

Pesquisa binária x Pesquisa simples 🥊

Vamos supor que tenho um número de 1 a 100 e você precisa adivinhar esse número com o menor número de tentativas possíveis. Isso é chamado de pesquisa simples, um método muito lento e ineficaz para buscar um resultado.

No pior cenário, levaríamos 100 tentativas para chegar ao resultado esperado. Portanto, vamos buscar de uma maneira melhor.
Para nos ajudar vamos definir alguns valores: máximo e mínimo. Onde o máximo = 100 (número total dos números) e mínimo = 0.
Vamos supor que o número que você precise adivinhar seja 91 e a cada tentativa vou informar se o número informado é menor ou maior que o resultado. Iremos iniciar nosso chute com o número 50 e com uma pequena fórmula: (min + max) / 2 = 50 onde o valor mínimo começa em 0 e o máximo é o número total. Podemos já notar que reduzimos o número de tentativas pela metade.
Certo! Nesse momento informo para você que o número que você chutou é menor que o resultado esperado, agora sabendo que nosso número é menor vamos atribuir o valor de 50 em nosso valor mínimo e somar + 1, dessa forma →
$51 + 100 / 2 = 75$

(OBS: Em nossa média sempre devemos arredondar nosso número para baixo)
75 agora é o valor do nosso chute, mas ainda não chegamos no resultado esperado, o resultado que queremos “adivinhar” é 92.
Nesse caso como nosso chute ainda foi menor que o resultado esperado, vamos repetir o processo de atribuir nosso chute em nosso valor mínimo e somar mais 1 para obter a média novamente, vamos lá!
$((75 + 1) + 100) / 2 = 88$

Ainda não chegamos, o valor continua baixo, vamos repetir o processo novamente!
$((88 + 1) + 100) / 2 = 94$

Humm, quase lá! Nesse caso nosso chute passou o valor esperado, quando o valor ultrapassa o resultado realizamos o oposto. Vamos atribuir o valor do chute no valor máximo e subtrair -1 para obter nossa média novamente.
→ Mantemos nosso valor mínimo e subtraímos -1 do valor do chute anterior substituindo nosso max.
$(89 + (94 - 1)) / 2 = 91$

E finalmente chegamos em nosso valor esperado.
Como podemos observar, comparando a busca com a pesquisa simples, reduzimos muitas etapas para chegar no número esperado.
E isso se trata de um algoritmo de pesquisa binária.

Implementação de um algoritmo de busca binária usando javascript

function binarySearch(array, element) {
    let low = 0
    let high = array.length - 1
    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        if (array[mid] === element) {
            return mid
        }
        if (array[mid] < element) {
            low = mid + 1
        } else {
            high = mid - 1
        }    
    }
    return null    
}

De acordo com o livro, de uma maneira geral, para uma lista de n números a pesquisa binária precisa de
$log_2n$ para retornar o valor correto, enquanto a pesquisa simples precisa de n etapas

Mas o que isso quer dizer ?

Se temos um array com 8 elementos, na busca binária vamos reduzindo o tamanho do array para 4, depois para 2 e por fim 1.
Então, com um array de comprimento 8 nossa busca binária precisa de no máximo quatro suposições onde acrescentamos + 1 em nossas suposições para garantir que todos os elementos do array sejam verificados.

O logaritmo é uma função matemática que representa o número de vezes que reduzimos pela metade um número de forma repetida, onde podemos escrever de uma forma mais adequada essa resolução.

Para explicar logaritmos também podemos falar sobre exponenciais, já que logaritmos são o oposto de exponenciais.

A expressão: $log_10(100)$ → (log de 100 na base 10) representa basicamente com quantos 10 podemos chegar a 100 e a resposta é 2, pois 10x10 = 100.
Podemos considerar esse outro exemplo ->
escrevendo como exponencial:
$aˆb = c$
escrevendo como logaritmo:
$log_a(c) = b$

Mas qual a diferença entre logaritmos e exponenciais ?

Na exponenciação conhecemos os valores de A e B, onde queremos obter o C e é isso que a exponenciação faz.
Já no logaritmo, sabemos quanto vale o A e queremos descobrir a qual potência deve elevar "A” para obter "C”, assim determinamos o "B”, são relações escritas de formas diferentes.
Fica claro no livro que quando falamos sobre Big O (onde será abordado no próximo capítulo) iremos utilizar $log_2$ (log na base de 2) por ser mais utilizado nos algoritmos que utiliza uma estratégia de "divisão e conquista”. Quando buscamos um elemento por pesquisa simples no pior dos cenários, necessitamos buscar elemento por elemento. Na pesquisa binária, precisamos verificar $log_n$ elementos para o pior dos casos.
Para uma lista de 1024 elementos, temos → $log_2 1024 == 10$ pois $2ˆ10 == 1024$
Dessa forma, uma lista de 1024 elementos através da pesquisa binária, precisaríamos verificar no máximo dez etapas.

💡Lembrando que para que a pesquisa binária funcione é necessário que a lista esteja ordenada, pois não é possível realizar busca por etapas caso a lista não esteja seguindo uma ordem.

Conclusão

Por fim, se você chegou até esta parte do artigo, espero que tenha gostado e caso tenha sugestões, melhorias, pode deixar nos comentários. Agradeço desde já.
Para ilustrar e demonstrar melhor um algoritmo de pesquisa binária, criei um jogo de adivinhação básico que contém algumas dicas e orientações de como chegar no número através da busca binária.
Link do projeto: https://jogo-adivinhacao-five.vercel.app/
Link do repositório no github: https://github.com/Giovanni-786/jogo-adivinhacao.

Referências

O conteúdo desse artigo foi tirado do livro "Entendendo algoritmos - Um guia ilustrado para programadores e outros curiosos", e da aula de busca binária da plataforma Khan academy