2.11 Observações Finais

Algoritmo de busca binária em um dicionário:

Passo 1 Abra o dicionário ao meio

Passo 2 Leia uma palavra

Passo 3 A palavra procurada foi encontrada? Se sim, escreva seu significado e ter

mine o algoritmo

Passo 4 O dicionário tinha apenas uma página? Se sim, escreva ‘Palavra não existe

’ e termine o algoritmo

Passo 5 Se a palavra procurada for menor que a palavra da página, descarte a part

e posterior do dicionário; se não, descarte a parte anterior do dicionário.

Passo 6 Chame o que restou de dicionário e vá para o passo 1

O passo 6 introduz um novo conceito. No início do algoritmo nosso universo de busca era o

dicionário. No passo 6, para poder repetir os mesmos passos apresentados anteriormente, dissemos que a metade que restou para a busca também se chama dicionário. Seria como se eu rasgasse o dicionário ao meio, jogasse a metade que eu sei que não pode conter a palavra que busco fora, e dissesse que a metade que me restou é o dicionário. Com este artifício, posso aplicar os mesmos passos anteriores, até encontrar ou não a palavra. Se o dicionário se reduzir a uma só página e eu não encontrar a palavra, é porque a palavra não existe.

Agora que temos uma boa base, vamos escrever o algoritmo em pseudocódigo:

Algoritmo de busca binária em um dicionário:

Repita:

Abra o dicionário ao meio

Leia uma palavra

Se a palavra lida for igual à palavra procurada:

Escreva seu significado

Termine o algoritmo

Se o dicionário tinha apenas uma página:

Escreva ‘Palavra não existe’

Termine o algoritmo

Se a palavra procurada for menor que a palavra lida:

descarte a parte posterior do dicionário

Se não:

descarte a parte anterior do dicionário.

Chame o que restou de dicionário

Estamos quase chegando a uma solução. O algoritmo já está bem melhor, mas ainda falta

formalizar a tomada de decisões e a repetição organizada de trechos de código. Esses assuntos serão tratados no próximo capítulo.

EXERCÍCIO 2.19

O algoritmo da busca binária apresentado nesta seção pode ser ainda mais re nado. Como fazer para acrescentar detalhes a

esse algoritmo?

2.11 OBSERVAÇÕES FINAIS

Neste capítulo apresentei diversos conceitos essenciais relativos aos dados e aos tipos básicos encontrados em qualquer linguagem de programação. Esses conceitos são a base do desenvolvimento de algoritmos. Deixei grande parte da sintaxe de Python em segundo plano. Se eu apresentasse todas as possibilidades da linguagem, em cada um dos itens, esse capítulo seria bem mais extenso. O pior seria termos relegado a um segundo plano os conceitos básicos da programação. Por exemplo, na formatação de números existem muito mais métodos de formatar dados. Mas acho que apresentar a sintaxe de Python, além de ser tedioso, iria desviar o foco do aprendizado. Releia o capítulo. Concentre-se nos conceitos. Você já deve ser capaz de escrever programas simples, em particular aqueles que envolvam apenas cálculos numéricos. Não se apresse. Aos poucos estamos construindo um pensamento algorítmico.

OceanofPDF.com