Pesquisa de Dados

Prévia do material em texto

CYAN
VS Gráfica VS Gráfica
MAG
VS Gráfica
YEL
VS Gráfica
BLACK
45505_Ciencia_da_Computacao_Brookshear.ps
D:\Produção\Grupo A\45505_Ciencia_da_Computacao_Brookshear\Abertos\45505_Ciencia_da_Computacao_Brookshear.cdr
quarta-feira, 20 de março de 2013 11:00:26
Perfil de cores: Desativado
Composição 175 lpi a 45 graus
Catalogação na publicação: Ana Paula M. Magnus – CRB10/2052
B873c Brookshear, J. Glenn.
 Ciência da computação [recurso eletrônico] : uma visão 
 abrangente / J. Glenn Brookshear ; contribuição: David T. 
 Smith, Dennis Brylow ; tradução: Eduardo Kessler Piveta. – 
 11. ed. – Dados eletrônicos. – Porto Alegre : Bookman, 2013.
 Editado também como livro impresso em 2013.
 ISBN 978-85-8260-031-3
 1. Ciência da computação. I. Título.
CDU 004
J. Glenn Brookshear é Ph.D. pela New Mexico State University e Professor 
Emérito da Marquette University, onde lecionou Linguagem Formal, 
Introdução à Ciência da Computação e Teoria da Computação.
170 Ciência da Computação: Uma Visão Abrangente
Concluímos que a descoberta de algoritmos permanece uma arte de-
safiadora que deve ser desenvolvida ao longo de um período de tempo, ao 
invés de ensinada como um assunto formado por metodologias bem defini-
das. De fato, treinar um solucionador de problemas para que ele siga certas 
metodologias é anular as características criativas que deveriam, ao invés 
disso, ser estimuladas.
Questões e exercícios
 1. a. Encontre um algoritmo para solucionar o seguinte problema: dado um inteiro positivo n, 
encontre a lista de inteiros positivos cujo produto seja o maior entre todas as listas de intei-
ros positivos cuja soma é n. Por exemplo, se n for 4, a lista desejada é 2, 2 porque 2 � 2 é 
maior que 1 � 1 � 1 � 1, 2 � 1 � 1 e 3 � 1. Se n for 5, a lista desejada é 2 e 3.
 b. Qual é a lista desejada se n � 2001?
 c. Explique como você deu o primeiro passo.
 2. a. Suponha que nos seja dado um tabuleiro de damas consistindo em 2n linhas e 2n colunas 
de quadrados, para algum inteiro positivo n, e uma caixa de ladrilhos em forma de L, cada 
um dos quais pode cobrir exatamente três quadrados do tabuleiro. Se qualquer quadrado for 
cortado do tabuleiro, podemos cobrir o tabuleiro restante com ladrilhos de forma que eles 
não se sobreponham ou caiam fora da borda do tabuleiro?
 b. Explique como sua solução para o item (a) pode ser usada para mostrar que 22n – 1 é divi-
sível por 3 para todos os inteiros positivos n.
 c. Como os itens (a) e (b) são relacionados às fases de Polya da resolução de problemas?
 3. Decodifique a mensagem a seguir, escrita em inglês, e então explique como você deu o pri-
meiro passo. Pdeo eo pda yknnayp wjosan.
 4. Você estaria seguindo uma metodologia descendente se tentasse resolver um quebra-cabeça 
simplesmente colocando as peças sobre a mesa e tentando agrupá-las? Sua resposta mudaria 
se você olhasse na caixa do quebra-cabeça para ver como é a imagem montada?
5.4 Estruturas iterativas
Nosso objetivo, agora, é estudar algumas das estruturas de repetição usadas 
para descrever processos algorítmicos. Nesta seção, discutiremos as estru-
turas iterativas, nas quais uma coleção de instruções é repetida na for-
ma de um laço. Na seção seguinte, introduziremos a técnica de recursão. 
Como consequência, introduziremos alguns algoritmos populares – a busca 
sequencial, a busca binária e a ordenação por inserção. Iniciamos introdu-
zindo o algoritmo de busca sequencial.
O algoritmo de busca sequencial
Considere o problema de buscar, dentro de uma lista de ocorrências, um va-
lor específico. Queremos desenvolver um algoritmo que determine se o va-
lor está na lista. Se o valor estiver na lista, consideramos a busca um suces-
so; caso contrário, a consideramos uma falha. Assumimos que a lista esteja 
ordenada de acordo com alguma regra de ordenação de suas entradas. Por 
exemplo, se for uma lista de nomes, assumimos que os nomes aparecem em 
Brookshear_05.indd 170Brookshear_05.indd 170 19/03/13 17:0119/03/13 17:01
Capítulo 5 Algoritmos 171
ordem alfabética; se a lista for formada por valores numéricos, assumimos 
que suas entradas aparecem em ordem crescente de magnitude.
Para dar o primeiro passo, imaginamos como poderíamos buscar, em 
uma lista de convidados com, digamos, 20 entradas, um nome em particu-
lar. Nesta configuração, poderíamos varrer a lista desde o início, comparando 
cada entrada com o nome buscado. Se achássemos o nome, a busca termina-
ria como um sucesso. Entretanto, se chegássemos ao final da lista sem encon-
trar o valor visado, nossa busca terminaria como uma falha. Na verdade, se 
alcançarmos um nome maior que (alfabeticamente) o nome alvo sem encon-
trar o alvo, nossa busca já termina como uma falha. (Lembre-se, a lista está 
organizada em ordem alfabética, então chegar a um nome maior que o nome 
alvo indica que o alvo não está na lista.) Em resumo, nossa ideia rudimentar é 
continuar buscando na lista enquanto existirem mais nomes a serem investi-
gados e o nome do alvo ser maior que o nome atualmente sendo considerado.
Em nosso pseudocódigo, esse processo poderia ser representado como
Selecione a primeira entrada na lista como EntradaDeTeste.
enquanto (ValorAlvo > EntradaDeTeste e
 existirem entradas remanescentes a serem consideradas)
 faça (Selecione a próxima entrada da lista como EntradaDeTeste)
Ao terminar essa estrutura enquanto, uma de duas condições será verdadei-
ra; ou o valor buscado foi encontrado ou não está na lista. Em cada um dos 
casos, podemos detectar uma busca bem-sucedida comparando a entrada 
de teste com o valor visado. Se eles forem iguais, a busca foi bem sucedida. 
Logo, adicionamos a seguinte sentença
se (ValorAlvo = EntradaDeTeste)
 então (Declare a busca um sucesso.)
 senão (Declare a busca uma falha.)
para terminar nossa rotina em pseudocódigo.
Por fim, observamos que a primeira sentença em nossa rotina, a qual 
seleciona a primeira entrada na lista como a entrada de testes, é baseada na 
premissa de que a lista em questão contém ao menos uma entrada. Pode-
mos argumentar que essa é uma suposição segura, mas apenas para termos 
certeza, podemos posicionar nossa rotina como a opção senão da sentença
se (Lista vazia)
 então (Declare a busca uma falha.)
 senão (...)
Isso produz o procedimento mostrado na Figura 5.6. Note que esse proce-
dimento pode ser usado de dentro de outros procedimentos por meio de 
sentenças como
Aplique o procedimento Buscar à lista de passageiros 
usando Darrel Baker como o valor a ser localizado.
para verificar se Darrel Baker é um passageiro e
Aplique o procedimento Buscar à lista de ingredientes 
usando noz-moscada como o valor a ser localizado.
Brookshear_05.indd 171Brookshear_05.indd 171 19/03/13 17:0119/03/13 17:01
172 Ciência da Computação: Uma Visão Abrangente
para encontrar se noz-moscada aparece na lista de ingredientes.
Em resumo, o algoritmo apresentado pela Figura 5.6 considera as en-
tradas na ordem sequencial pela qual elas ocorrem na lista. Por essa razão, 
o algoritmo é chamado de algoritmo de busca sequencial. Por sua simpli-
cidade, ele é frequentemente usado para pequenas listas ou quando outras 
preocupações ditam seu uso. Entretanto, no caso de listas longas, as buscas 
sequenciais não são tão eficientes quanto outras técnicas (que veremos em 
breve).
Controle de laços
O uso repetitivo de uma instrução ou de uma sequência de instruções é 
um conceito algorítmico importante. Um método de implementar tal repe-
tição é a estrutura iterativa conhecida como laço, na qual uma coleção de 
instruções, chamada de corpo do laço, é executada de maneira repetida sob 
a direção de algum processo de controle. Um exemplo típico é encontrado 
no algoritmo de busca sequencial representado na Figura 5.6. Neste caso, 
usamos uma sentença enquanto para controlar a repetição da sentença úni-
ca Selecione a próxima entrada da lista como EntradaDeTeste. Na 
verdade, a sentença enquanto
enquanto (condição) faça (corpo)
exemplificao conceito de uma estrutura de laço, já que sua execução mostra 
o padrão cíclico
verificar a condição.
executar o corpo.
verificar a condição.
executar o corpo.
 .
 .
 .
verificar a condição.
até que a condição falhe.
procedimento Buscar(Lista, ValorAlvo)
se (Lista vazia) 
 então
 (Declare a busca uma falha.)
 senão
 (Selecione a primeira entrada na lista como sendo EntradaDeTeste;
 enquanto (ValorAlvo > EntradaDeTeste e
 existirem entradas remanescentes a serem consideradas)
 faça (Selecione a próxima entrada da lista como EntradaDeTeste.);
 se (ValorAlvo = EntradaDeTeste)
 então (Declare a busca um sucesso.)
 senão (Declare a busca uma falha.)
 ) fim se
Figura 5.6 Algoritmo de busca sequencial em pseudocódigo.
Brookshear_05.indd 172Brookshear_05.indd 172 19/03/13 17:0119/03/13 17:01
Capítulo 5 Algoritmos 181
5.5 Estruturas recursivas
Estruturas recursivas fornecem ao paradigma de laços uma alternativa para 
implementar a repetição de atividades. Enquanto um laço implica repetir 
um conjunto de instruções de maneira que o conjunto seja completado e en-
tão repetido, a recursão envolve repetir o conjunto de instruções como uma 
tarefa em si mesma. Como uma analogia, considere o processo de conduzir 
conversas telefônicas com o recurso de espera de chamada. Uma conversa 
telefônica incompleta é posta de lado enquanto outra chamada é processa-
da. O resultado é que duas conversas estarão ocorrendo. Entretanto, elas 
não são realizadas uma após a outra, como em uma estrutura de laço, mas, 
em vez disso, uma é realizada dentro da outra.
O algoritmo de busca binária
Como uma maneira de introduzir recursão, vamos mais uma vez tratar 
do problema da busca por uma entrada específica em uma lista ordenada, 
mas, desta vez, damos o primeiro passo considerando o procedimento que 
seguimos quando buscamos em um dicionário. Neste caso, não realizamos 
um procedimento entrada por entrada ou página por página. Ao invés dis-
so, começamos abrindo o dicionário em uma página que esteja em uma 
área na qual acreditamos que a entrada buscada esteja localizada. Se ti-
vermos sorte, encontraremos o valor visado lá; caso contrário, devemos 
continuar a busca. Ainda assim, neste ponto, já reduzimos nossa busca 
consideravelmente.
Obviamente, quando fazemos uma busca em um dicionário, temos um 
conhecimento prévio de palavras que provavelmente serão encontradas. 
Se você estiver procurando pela palavra sonambulismo, iniciaria abrindo a 
porção mais ao fim do dicionário. No caso de listas genéricas, entretanto, 
não temos essa vantagem, então vamos estabelecer um consenso de sempre 
Lista original
Primeira 
sublista
Segunda 
sublista
Alice
Bob
Carol
David
Elaine
Fred
George
Harry
Irene
John
Kelly
Larry
Mary
Nancy
Oliver
Irene
John
Kelly
Larry
Mary
Nancy
Oliver
Irene
John
Kelly
Figura 5.12 Aplicação da nossa estratégia para buscar a entrada John em uma lista.
Brookshear_05.indd 181Brookshear_05.indd 181 19/03/13 17:0219/03/13 17:02
182 Ciência da Computação: Uma Visão Abrangente
iniciar nossa busca pela entrada localizada no “meio” da lista. Aqui, escre-
vemos a palavra meio entre aspas porque a lista pode ter um número par 
de entradas e, logo, nenhuma entrada do meio existirá de fato. Neste caso, 
vamos convencionar que a entrada do “meio” se refere à primeira entrada 
da segunda metade da lista.
Se a entrada no meio da lista for o valor buscado, podemos declarar a 
busca um sucesso. Caso contrário, podemos ao menos restringir o processo 
de busca para a primeira ou para a segunda metade da lista, dependendo de 
o valor buscado ser menor ou maior que a entrada que estamos consideran-
do. (Lembre-se de que a lista é ordenada.)
Para buscar na porção remanescente da lista, poderíamos aplicar a 
busca sequencial, mas ao invés disso vamos aplicar a mesma abordagem 
para essa porção da lista que usamos para a lista inteira. Ou seja, selecio-
namos a entrada do meio na porção remanescente da lista como a próxima 
entrada a ser considerada. Como antes, se esta entrada for o valor visado, 
terminamos. Caso contrário, podemos restringir nossa busca para uma por-
ção ainda menor da lista.
Essa abordagem para o processo de busca é resumida na Figura 5.12, 
na qual consideramos a tarefa de fazer uma busca na lista mais à esquerda 
na figura, pela entrada John. Primeiro, consideramos a entrada do meio, 
Harry. Como nosso alvo está após esta entrada, a busca continua, conside-
rando a metade inferior da lista original. O meio da sublista agora é calcu-
lado como Larry. Como nosso alvo deve preceder Larry, movemos nossa 
atenção para a primeira metade da sublista atual. Quando interrogamos o 
meio desta sublista secundária, encontramos nosso alvo, John, e declara-
mos a busca um sucesso. Em resumo, nossa estratégia é dividir sucessiva-
mente a lista em segmentos menores, até que o alvo seja encontrado ou a 
busca esteja restrita a um segmento vazio.
Precisamos enfatizar esse último ponto. Se o valor buscado não estiver 
na lista original, nossa abordagem para a busca na lista será conduzida ao di-
se (Lista vazia)
 então 
 (Relate que a busca falhou.)
 senão
 [Selecione a entrada do “meio” da Lista como sendo a EntradaDeTeste;
 Execute o bloco de instruções abaixo que 
 está associado com o caso apropriado.
 caso 1: ValorAlvo = EntradaDeTeste
 (Relate que a busca foi bem-sucedida.)
 caso 2: ValorAlvo < EntradaDeTeste
 (Busque a porção da lista anterior a EntradaDeTeste pelo
 ValorAlvo e relate o resultado dessa busca.)
 caso 3: ValorAlvo > EntradaDeTeste
 (Busque a porção da lista após EntradaDeTeste pelo
 ValorAlvo, e relate o resultado dessa busca.)
 ] fim se
Figura 5.13 Primeiro rascunho da técnica de busca binária.
Brookshear_05.indd 182Brookshear_05.indd 182 19/03/13 17:0219/03/13 17:02
Capítulo 5 Algoritmos 183
vidirmos a lista em segmentos menores até que o segmento que está sendo 
considerado esteja vazio. Nesse momento, nosso algoritmo deve reconhecer 
que a busca falhou.
A Figura 5.13 é um primeiro rascunho de nossos pensamentos usando 
nosso pseudocódigo. Ele nos conduz a começar uma busca tentando ver 
se a lista está vazia. Se estiver, ele nos diz para relatar que a busca é uma 
falha. Caso contrário, o rascunho nos diz para considerar a entrada do meio 
da lista. Se a entrada não for o valor buscado, ele nos diz para buscar na 
primeira metade ou na segunda metade da lista. Ambas as possibilidades 
requerem uma busca secundária. Seria bom realizar essas buscas por meio 
de chamadas aos serviços de uma ferramenta abstrata. Em particular, nossa 
abordagem é aplicar um procedimento chamado Buscar para conduzir essas 
buscas secundárias. Para completar nosso programa, logo, devemos forne-
cer tal procedimento.
No entanto, esse procedimento deve realizar a mesma tarefa expressa 
pelo pseudocódigo que já escrevemos. Ele primeiro deve verificar se a lista 
Busca e ordenação
Os algoritmos de busca sequencial e de busca binária são apenas dois dos muitos algoritmos 
para realizar o processo de busca. De maneira similar, a ordenação por inserção é apenas um de 
muitos algoritmos de ordenação. Outros algoritmos clássicos para ordenação incluem a ordena-
ção por mesclagem (merge sort), discutida no Capítulo 12, a ordenação por seleção (Questão/
Exercício 6 da Seção 5.4), a ordenação por bolha (Questão/Exercício 7 da Seção 5.4), a ordena-
ção rápida (quick sort), que aplica uma abordagem dividir para conquistar sobre o processo de 
ordenação) e a ordenação por monte (heap sort), que usa uma técnica bastante inteligente para 
encontrar as entradas que devem ser movidas para frente na lista. Você encontrará discussões 
sobre esses algoritmos nos livros listados na Leitura Adicional, ao final deste capítulo.
procedimento Buscar (Lista, ValorAlvo)
se (Listavazia)
 então 
 (Relate que a busca falhou.)
 senão
 [Selecione a entrada do “meio” da Lista como sendo a EntradaDeTeste;
 Execute o bloco de instruções abaixo que 
 está associado com o caso apropriado.
 caso 1: ValorAlvo = EntradaDeTeste
 (Relate que a busca foi bem sucedida.)
 caso 2: ValorAlvo < EntradaDeTeste
 (Aplique o procedimento Buscar para ver se ValorAlvo
 está na porção da lista anterior a EntradaDeTeste, 
 e relate o resultado dessa busca.)
 caso 3: ValorAlvo > EntradaDeTeste
 (Aplique o procedimento Buscar para ver se ValorAlvo
 está na porção da lista posterior a EntradaDeTeste, 
 e relate o resultado dessa busca.)
 ] fim se
Figura 5.14 Algoritmo de busca binária em pseudocódigo.
Brookshear_05.indd 183Brookshear_05.indd 183 19/03/13 17:0219/03/13 17:02
184 Ciência da Computação: Uma Visão Abrangente
que ele recebeu está vazia e, se não estiver, ele deve continuar considerando 
a entrada do meio dessa lista. Logo, podemos fornecer o procedimento que 
precisamos simplesmente identificando a rotina atual como o procedimento 
chamado Buscar e inserindo referências para esse procedimento, no qual as 
buscas secundárias são requeridas. O resultado é mostrado na Figura 5.14.
Note que esse procedimento contém uma referência para si mesmo. Se 
o estivéssemos seguindo e chegássemos na instrução
Aplique o procedimento Buscar...
aplicaríamos na lista menor o mesmo procedimento que estávamos aplican-
do na lista original. Se essa busca fosse bem sucedida, retornaríamos para 
declarar que nossa busca original havia sido bem sucedida; se essa busca 
secundária falhasse, declararíamos que nossa busca original falhou.
Para ver como o procedimento na Figura 5.14 realiza sua tarefa, vamos 
segui-lo enquanto ele faz uma busca na lista Alice, Bill, Carol, David, Evelyn, 
Fred e George, pelo valor Bill. Nossa busca começa selecionando David (a 
entrada do meio) como a entrada de teste a ser considerada. Como o valor 
buscado (Bill) é menor que essa entrada de teste, o algoritmo nos instrui 
para aplicar o procedimento Buscar na lista de entradas que precede David 
– ou seja, a lista Alice, Bill e Carol. Ao fazer isso, criamos uma segunda cópia 
do procedimento de busca e atribuímos a ela essa tarefa secundária.
Agora, temos duas cópias de nosso procedimento de busca sendo exe-
cutadas, como resumido na Figura 5.15. O progresso na cópia original é tem-
porariamente suspenso na instrução
(EntradaDe
Teste)
Lista
David
Evelyn
Fred
George
David
Evelyn
Fred
George
David
Evelyn
Fred
George
Lista
Alice
Bill
Carol
Estamos aqui.
procedimento Buscar (Lista, ValorAlvo)
se (Lista vazia)
 então
 
 (Relate que a busca falhou.)
 
 senão
 [Selecione a entrada do “meio” da Lista como sendo a EntradaDeTeste;
 Execute o bloco de instruções abaixo que 
 está associado com o caso apropriado.
 caso 1: ValorAlvo = EntradaDeTeste
 (Relate que a busca foi bem sucedida.)
 caso 2: ValorAlvo < EntradaDeTeste
 (Aplique o procedimento Buscar para ver se ValorAlvo
 está na porção da lista anterior a EntradaDeTeste, 
 e relate o resultado dessa busca.)
 caso 3: ValorAlvo > EntradaDeTeste
 (Aplique o procedimento Buscar para ver se ValorAlvo
 está na porção da lista posterior a EntradaDeTeste, 
 e relate o resultado dessa busca.)
 ] fim se
procedimento Buscar (Lista, ValorAlvo)
se (Lista vazia)
 então
 
 (Relate que a busca falhou.)
 
 senão
 [Selecione a entrada do “meio” da Lista como sendo a EntradaDeTeste;
 Execute o bloco de instruções abaixo que 
 está associado com o caso apropriado.
 caso 1: ValorAlvo = EntradaDeTeste
 (Relate que a busca foi bem sucedida.)
 caso 2: ValorAlvo < EntradaDeTeste
 (Aplique o procedimento Buscar para ver se ValorAlvo
 está na porção da lista anterior a EntradaDeTeste, 
 e relate o resultado dessa busca.)
 caso 3: ValorAlvo > EntradaDeTeste
 (Aplique o procedimento Buscar para ver se ValorAlvo
 está na porção da lista posterior a EntradaDeTeste, 
 e relate o resultado dessa busca.)
 ] fim se
Figura 5.15
Brookshear_05.indd 184Brookshear_05.indd 184 19/03/13 17:0219/03/13 17:02
Capítulo 5 Algoritmos 185
Aplique o procedimento Buscar para ver se ValorAlvo
está na porção da lista anterior a EntradaDeTeste,
enquanto aplicamos a segunda cópia à tarefa de buscar na lista Alice, Bill 
e Carol. Quando completarmos essa busca secundária, descartaremos a se-
gunda cópia do procedimento, relataremos suas descobertas para a cópia 
original e continuamos o progresso na original. Dessa maneira, a segun-
da cópia do procedimento funciona como uma sub-rotina da original, reali-
zando a tarefa solicitada pelo módulo original e, então, desaparecendo.
A busca secundária seleciona Bill como sua entrada de teste, pois ela é 
a entrada do meio na lista Alice, Bill e Carol. Como ela é igual ao valor bus-
cado, ela declara sua busca um sucesso e termina.
Neste ponto, completamos a busca secundária, como solicitado pela 
cópia original do procedimento, e somos capazes de continuar a execução 
dessa cópia original. Aqui, o algoritmo nos diz que o resultado da busca se-
cundária deve ser relatado como sendo o resultado da busca original. Logo, 
relatamos que a busca original foi bem-sucedida. Nosso processo determi-
nou corretamente que Bill é um membro da lista Alice, Bill, Carol, David, 
Evelyn, Fred e George.
Vamos agora considerar o que acontece se pedirmos ao procedimento 
na Figura 5.14 para buscar, na lista Alice, Carol, Evelyn, Fred e George, pela 
entrada David. Desta vez, a cópia original do procedimento seleciona Eve-
lyn como sua entrada de teste e conclui que o valor buscado deve residir na 
seção anterior da lista. Ele, então, requer outra cópia do procedimento para 
buscar a lista de entradas que aparecem na frente de Evelyn – ou seja, a lista 
de duas entradas que consiste em Alice e Carol. Neste estágio, nossa situa-
ção está conforme representado na Figura 5.16.
A segunda cópia do procedimento seleciona Carol como sua entrada 
atual e conclui que o valor buscado deve residir na porção posterior de sua 
lista. Ela, então, requer uma terceira cópia do procedimento para buscar a 
lista de nomes que seguem Carol na lista Alice e Carol. Essa sub-lista é vazia, 
então a terceira cópia do procedimento tem a tarefa de buscar na lista vazia 
pelo valor David. Nossa situação neste ponto é representada pela Figura 
5.17. A cópia original do procedimento recebe a tarefa de buscar na lista 
Alice, Carol, Evelyn, Fred e George, com a entrada de teste sendo Evelyn; a 
segunda cópia recebe a tarefa de buscar na lista Alice e Carol, com sua en-
trada de teste sendo Carol; e a terceira cópia trata de começar a buscar em 
uma lista vazia.
Obviamente, a terceira cópia do procedimento rapidamente declara que 
sua busca foi uma falha e termina. O término da tarefa da terceira cópia permi-
te que a segunda cópia continue sua tarefa. Ela nota que a busca que ela requi-
sitou não foi bem sucedida, declara que sua própria tarefa foi uma falha e ter-
mina. Esse relato é o que a cópia original do procedimento estava esperando, 
então ela pode prosseguir. Como a busca que ela requisitou falhou, ela declara 
que sua própria busca falhou e termina. Nossa rotina concluiu corretamente 
que David não está na lista Alice, Carol, Evelyn, Fred e George.
Em resumo, se voltássemos a olhar os exemplos anteriores, podería-
mos ver que o processo empregado pelo algoritmorepresentado na Figura 
5.14 é dividir a lista em questão repetidamente em duas porções menores, 
de maneira que a busca remanescente pudesse estar restrita a apenas uma 
Brookshear_05.indd 185Brookshear_05.indd 185 19/03/13 17:0219/03/13 17:02
186 Ciência da Computação: Uma Visão Abrangente
dessas duas peças. Essa abordagem de divisão por dois é a razão pela qual o 
algoritmo é conhecido como a busca binária.
Controle recursivo
O algoritmo de busca binária é similar à busca sequencial no sentido de que 
cada algoritmo requer a execução de um processo repetitivo. Entretanto, a 
implementação dessa repetição é significativamente diferente. Enquanto a 
busca sequencial envolve uma forma circular de repetição, a busca binária 
executa cada estágio da repetição como uma subtarefa do estágio anterior. 
Essa técnica é conhecida como recursão.
Como vimos, a ilusão criada pela execução de um procedimento recur-
sivo é a da existência de múltiplas cópias do procedimento, cada uma das 
quais é chamada de uma ativação do procedimento. Essas ativações são cria-
das dinamicamente em uma maneira telescópica e, por fim, desaparecem à 
medida que o algoritmo avança. Das ativações existentes em dado momen-
to, apenas uma está ativamente progredindo. As outras estão efetivamente 
no limbo, cada uma delas esperando pelo término de outra ativação antes 
de poder continuar.
Sendo um processo repetitivo, os sistemas recursivos são tão depen-
dentes de controles apropriados quanto são as estruturas de laço. Assim 
como no controle de laço, os sistemas recursivos são dependentes de testes 
em relação a uma condição de término e de um projeto que garanta que 
essa condição seja alcançada. Na verdade, um controle recursivo apropriado 
(EntradaDe
Teste)
Lista
Evelyn
Fred
George David
Evelyn
Fred
George
David
Evelyn
Fred
George
Lista
Alice
Carol
Estamos aqui.
procedimento Buscar (Lista, ValorAlvo)
se (Lista vazia)
 então
 
 (Relate que a busca falhou.)
 
 senão
 [Selecione a entrada do “meio” da Lista como sendo a EntradaDeTeste;
 Execute o bloco de instruções abaixo que 
 está associado com o caso apropriado.
 caso 1: ValorAlvo = EntradaDeTeste
 (Relate que a busca foi bem sucedida.)
 caso 2: ValorAlvo < EntradaDeTeste
 (Aplique o procedimento Buscar para ver se ValorAlvo
 está na porção da lista anterior a EntradaDeTeste, 
 e relate o resultado dessa busca.)
 caso 3: ValorAlvo > EntradaDeTeste
 (Aplique o procedimento Buscar para ver se ValorAlvo
 está na porção da lista posterior a EntradaDeTeste, 
 e relate o resultado dessa busca.)
 ] fim se
procedimento Buscar (Lista, ValorAlvo)
se (Lista vazia)
 então
 
 (Relate que a busca falhou.)
 
 senão
 [Selecione a entrada do “meio” da Lista como sendo a EntradaDeTeste;
 Execute o bloco de instruções abaixo que 
 está associado com o caso apropriado.
 caso 1: ValorAlvo = EntradaDeTeste
 (Relate que a busca foi bem sucedida.)
 caso 2: ValorAlvo < EntradaDeTeste
 (Aplique o procedimento Buscar para ver se ValorAlvo
 está na porção da lista anterior a EntradaDeTeste, 
 e relate o resultado dessa busca.)
 caso 3: ValorAlvo > EntradaDeTeste
 (Aplique o procedimento Buscar para ver se ValorAlvo
 está na porção da lista posterior a EntradaDeTeste, 
 e relate o resultado dessa busca.)
 ] fim se
Figura 5.16
Brookshear_05.indd 186Brookshear_05.indd 186 19/03/13 17:0219/03/13 17:02
Encerra aqui o trecho do livro disponibilizado para 
esta Unidade de Aprendizagem. Na Biblioteca Virtual 
da Instituição, você encontra a obra na íntegra.
	Página em branco