Responde Aí

Exercícios Resolvidos de Algoritmos

Ver Teoria

Enunciado

O Dexter, mascote do Responde Aí, precisa encontrar uma palavra no dicionário, mas o dicionário tem UM MONTE de palavras. Escreva um algoritmo que ajude o dexter a encontrar a palavra sem ter que ler de uma em uma.

Passo 1

Fala aí, pequeno gafanhoto!! Bom, antes da gente começar a discutir sobre os algoritmos, vamos relembrar que não existe só um algoritmo pra realizar algum trabalho. Existem váaarias respostas pra essa questão, mas também é legal lembrar que o ideal é que a gente tenha o mínimo de trabalho possível, beleza?

Então vamo lá! Vamos supor que você pegou aí um dicionário. Se você simplesmente abrisse ele e fosse lendo palavra por palavra, você encontraria, com certeza, aquela que você procura. Mas tem dois pontos importantes nesse método: se a palavra for com A você vai achar rapidinho, mas se for com Z, aí ferrou.

Imagina que seu dicionário tem 30 mil palavras. No melhor dos casos, você checaria 1 palavra (caso fosse a primeira). No pior dos casos, você verificaria 30 mil fucking palavras (caso fosse a última).

Não é um algoritmo muito bom, né? Realmente, precisamos de uma alternativa. Considerando que o dicionário é organizado em ordem alfabética, olha o passo a passo que eu coloquei aqui embaixo:

  • Abrir o dicionário na página do meio e ler a primeira palavra.
  • Se a palavra for alfabeticamente maior
  • Descartar a parte direita do dicionário e recomeçar o algoritmo
  • Se a palavra for alfabeticamente menor
  • Descartar a parte esquerda do dicionário e recomeçar o algoritmo

Viu? Quando esse algoritmo chegar no fim, significa que você encontrou a palavra. Esse algoritmo, baseado na subdivisão de um conjunto ordenado de dados é chamado de Busca Binária.

Olha como ficaria, matematicamente:

Ou seja, você vai dividir tudo por dois até sobrar só uma, que é a que você procura. O n é a quantidade de vezes que a gente precisa dividir por dois. Pra gente descobrir ele, vamos resolver a equação:

Olha que doideira! Com esse método, no pior dos casos você só precisa ler 15 (QUINZE) palavras. No melhor dos casos, continua sendo 1. Viu a trabalheira que a gente evitou, só parando pra pensar num algoritmo??

Beleza, terminamos! Hahaha valeuuuu!

Resposta

  • Abrir o dicionário na página do meio e ler a primeira palavra.
  • Se a palavra for alfabeticamente maior
  • Descartar a parte direita do dicionário e recomeçar o algoritmo
  • Se a palavra for alfabeticamente menor
  • Descartar a parte esquerda do dicionário e recomeçar o algoritmo