Bem vindo ao curso de Introdução à Ciência da Computação destinado aos alunos regulares da Universidade de São Paulo! Esta é a segunda parte do Curso, onde você vai continuar a aprender os principais conceitos introdutórios de Ciência da Computação e também aprenderá a desenvolver pequenos programas na linguagem Python. Esta disciplina não possui pré-requisitos; não é esperado que você tenha qualquer experiência prévia em programação; ela exige apenas o conhecimento dos conceitos básicos de matemática do ensino fundamental. No entanto, você deve fazer a primeira parte do Curso (também disponível aqui no Coursera). O objetivo principal é desenvolver o raciocínio aplicado na formulação e resolução de problemas computacionais, ensinar como abordar e resolver problemas computacionais. O ato de programar é uma ferramenta útil para trabalhar o raciocínio mencionado acima, bem como tornar mais concretos outros conceitos comuns em ciência da computação. Ao término do curso, o aluno estará capacitado para escrever pequenos programas em Python e a continuar com estudos mais avançados sobre Python por conta própria usando material disponível na Web. Bom curso!
Busca Binária
Loading...
Do curso por Universidade de São Paulo
Introdução à Ciência da Computação com Python Parte 2
255 classificações
Na lição
Algoritmos de Busca e Ordenação. Análise de Desempenho
Legal, estamos chegando no final. Nessa semana iremos ver mais um pouco sobre algoritmos de busca e ordenação, além de testes automatizados. Bom trabalho!
Conheça os instrutores
Fabio KonProfessor Titular
Departamento de Ciência da Computação - IME
[MÚSICA] Dos meus algoritmos preferidos é a busca binária,
que é algoritmo muito interessante que é utilizado para achar,
de uma forma muito rápida, determinado elemento numa lista ou num vetor
quando esses elementos já estão ordenados.
A gente já viu algoritmos de ordenação, então a gente pode ordenar a lista e
depois a busca nessa lista onde os elementos estão ordenados.
Como que a gente poderia levar isso consideração para ter
algoritmo bem eficiente?
A gente viu que a busca sequencial não é muito eficiente.
Naquele exemplo que a gente viu de uma lista telefônica com dois milhões de
elementos ter que ficar percorrendo todos os elementos ali sequencialmente,
faz demorar muito tempo,
ninguém iria aguentar esperar uma busca dessas numa lista telefônica, não é?
Então a gente poderia levar conta o fato de que a lista está
ordenada e daí achar as coisas de uma forma mais rápida.
Como a gente poderia fazer isso?
É bom pensar no algoritmo da busca binária.
O objetivo aqui então é localizar elemento x,
vamos supor que é número, numa lista de números.
Considere então o elemento m do meio da lista.
Eu estou falando aqui número só para simplificar, mas poderia ser uma lista de
CDs, uma lista de times do Campeonato Brasileiro, uma lista de qualquer coisa.
Vamos pensar números, só para ficar mais fácil.
Então vamos supor que m é o elemento,
tem uma lista aqui e eu pego o elemento bem do meio da lista.
E eu estou procurando o x.
O que eu posso fazer?
Tem três casos: se x é igual a m, daí pronto, eu já achei o elemento x,
é só eu dizer que o x está nessa posição aqui, m da lista.
Por outro lado, pode ser que x seja menor que m.
Se x for menor que m e a lista está ordem,
significa que o x está aqui na primeira metade, na metade da esquerda dessa lista.
Eu posso jogar fora a parte da direita e refazer a busca binária só nesse pedaço,
na primeira metade aqui da esquerda.
E o terceiro caso é que x é maior que m.
Se x é maior que m, como a lista está ordem,
quer dizer que o x está à direita, está na segunda metade aqui da lista.
E eu posso ir repetindo esse processo até que o x seja encontrado.
Então começo com a lista completa aqui, daí comparo com o meio,
daí a cada iteração eu jogo metade da lista fora.
Então vamos supor que eu joguei fora esse pedaço, eu fico só com esse pedaço, daí eu
olho só para esse pedaço aqui, comparo com o elemento ali do meio, o x do meio.
Por exemplo, se x for maior, daí eu pego só esse pedaço e divido por dois de novo,
depois divide por dois de novo.
Vai dividindo por dois, até que momento ou eu acho o elemento,
ou eu chego num momento que a lista ficou vazia.
Eu fui dividindo tanto por dois que a lista ficou ali vazia.
Então como a gente pode implementar Python algoritmo dessa forma?
Vamos dar uma olhada aqui.
Eu abri então aqui a classe Buscador, que eu tinha implementado antes com
a busca sequencial, eu vou passar a implementar aqui também a busca binária.
Busca binária, eu vou receber como
parâmetro a lista e elemento x que eu quero buscar na lista.
Então como eu vou fazer isso?
Primeira coisa, eu tenho que saber, iii a gente está iii, a gente sempre está
trabalhando com pedaço da lista e a gente sempre vai dividindo por dois.
Então eu quero saber quem é esse pedaço,
esse pedaço eu vou ter duas variáveis que vão apontar para o
primeiro elemento do pedaço e o último, que eu vou chamar de primeiro e último.
Então o primeiro, inicialmente eu quero que o primeiro seja o,
eu quero na primeira iteração analisar a lista completa.
Então o primeiro vai ser o primeiro elemento da lista,
que é o índice zero e o último vai ser o último elemento da lista,
que é o comprimento da lista menos.
Então o primeiro e o último na primeira iteração comportam a lista
inteira e depois,
a cada iteração eu vou mudando-os para dividir pela metade o tamanho da lista.
Então eu vou fazer o seguinte: enquanto,
eu vou querer repetir enquanto ainda tem algo entre primeiro e último,
porque vai chegar momento que eles vão diminuindo e que eles vão ficar,
vão passar o primeiro vai ficar maior que o último,
porque daí quer dizer que a sublista é vazia e daí eu não achei o meu elemento.
Então eu continuo a execução enquanto o primeiro é menor ou igual ao último,
porque enquanto o primeiro é menor ou igual ao último ainda tem algum
elemento dentro dessa minha sublista.
Daí o que eu faço?
Aí eu vou calcular quem é o elemento que está no meio, qual é o índice do meio.
O índice do meio vai ser, é fácil: primeiro mais último dividido por dois.
Primeiro mais último dividido por dois.
Eu só tenho que tomar cuidado, porque essa divisão por dois,
se o primeiro mais último for número ímpar,
vai dar índice ponto cinco, que não faz sentido índice ponto cinco.
Então eu tenho que pegar uma divisão inteira do dois, ou eu posso colocar int
aqui antes disso ou, Python tem esse barra barra, que já faz a divisão inteira.
Agora eu vou comparar.
Se o elemento que está lá no meio da lista é igual a x,
aí pronto eu achei, achei onde está o x e eu simplesmente
devolvo o índice onde eu estou achando o x, que é o meio.
Então esse é o caso feliz que eu achei o meu elemento que eu estou procurando.
Caso contrário, se eu não achei, o que pode acontecer?
Aí tem dois casos: ou o x é menor que o elemento que está lá no meio da lista e,
se ele é menor, daí eu tenho que procurar na metade esquerda,
na primeira metade da lista, não é?
Para procurar na metade esquerda, o que eu vou fazer?
Eu vou pegar o último, vez de ser o último anterior,
o último vai ser uma posição à esquerda do meio.
Então eu vou fazer isso aqui: último recebe meio menos.
Eu não preciso colocar no meio, porque no meio eu já vi que não é.
Então uma posição antes do meio, o último vai ser o meio menos.
Caso contrário, ou seja, se não é nem,
lista de meio não é igual a x e não é menor que x, significa que é maior que x.
Se é maior que x, daí eu tenho que procurar na metade da direita.
Como eu posso fazer?
Eu vou fazer a variável primeiro ir para uma depois do meio.
Primeiro recebe meio mais
eu não preciso olhar mais para o meio, porque o meio eu já vi que não é.
Então daí eu vou repetindo isso.
Se algum momento eu acho, daí esse comando if
já vai fazer o return e devolver que posição que achou.
Se por acaso vai diminuindo, diminuindo, diminuindo, diminuindo,
esse meio menos e esse meio mais aqui vão fazer algum momento,
aqui estão o último e o primeiro, algum momento eles vão trocar assim, o último
vai ficar menor que o primeiro e daí quer dizer que o elemento não está na lista.
Então daí eu posso devolver para indicar que o elemento não está na lista aqui.
Então se cai fora desse while aqui, eu posso indicar que,
com devolvendo menos que o elemento não está na lista.
Então vamos executar aqui, fazer pequeno teste.
Vamos primeiro criar uma lista,
tem que ser uma lista ordenada, com alguns elementos aqui.
[SEM_ÁUDIO] Aqui está o.k.
essa minha lista aqui, uma lista ordenada com esses elementos,
e agora eu vou querer chamar aqui a minha busca binária.
Então eu vou criar buscador, eu vou chamar esse buscador de
buscador de b e gora fazer b ponto busca binária.
Eu quero que você busque nessa minha,
eu vou chamar lista, elemento, vamos supor o elemento 100.
Primeiro eu vou ver o que está na posição 5, que é esse mesmo?
Deixa eu ver zero, dois três quatro cinco certo.
O 100 está na posição 5.
Eu vou fazer mais alguns testes aqui.
Se eu buscar o elemento 0, está na posição.
Se eu buscar o elemento menos 100, está na posição zero, certo.
Se eu buscar o elemento 5000, está na posição, certo.
O tamanho da lista é oito.
Então o tamanho da lista é oito, os elementos vão de zero a sete,
então sete é o último, está certo, 5000 é o último.
Agora uma coisa importante: nós vamos buscar o que não está lista.
Então 7000 iii devolveu menos para dizer que não está na lista.
Vamos pegar o 70, 70 não está na lista.
Também ali devolveu menos para dizer que não está na lista.
Então esse aqui é o algoritmo da busca binária.
Agora qual será que é a complexidade computacional do algoritmo da
busca binária?
Pensar o seguinte: eu lembro quando eu era criança,
eu adorava uma série do Carl Sagan, astrônomo americano,
chamada Cosmos e tem episódio onde ele fala, ele segura uma maçã na mão e fala:
"Se você dividir essa maçã dois aqui, quantas vezes você precisa dividir
a maçã dois até chegar no átomo?" E a resposta era surpreendente.
Ele dizia que era 80.
Se você cortar uma maçã dois 80 vezes, sempre na metade,
80 vezes, você chega num único átomo.
Isso ele estava querendo dizer que uma
maçã tem cerca de dois elevado a 80 átomos.
Então se a gente pensar que uma maçã tem dois elevado a 80 átomos,
quantas vezes a gente consegue dividir por dois a maçã?
80 vezes.
Isso na verdade é o log de 80, de dois elevado a 80 na base dois, que é o 80.
Então se a gente pensar na busca binária, dada uma lista de n elementos,
quantas vezes a gente vai ter que fazer essa comparação,
quantas vezes deve executar esse while aqui até chegar num único elemento,
que é o pior caso, é a gente ter que cortar essa lista
dois várias vezes até chegar num único elemento.
Se a lista tem n elementos,
quantas vezes a gente consegue cortar dois até chegar apenas?
E na verdade é log de n na base 2.
Então a gente vai ter que, no pior dos casos, fazer log de n na base dois
comparações ali do x com o meio para encontrar esse elemento.
Se a gente lembrar naquele exemplo da lista telefônica,
que era uma lista telefônica de dois milhões de elementos,
e eu dizia que cada comparação por exemplo demorava milissegundo e a gente viu que
a busca sequencial demorava muito tempo, vários minutos para encontrar.
No caso da busca binária, eu calculei aqui usando uma calculadora,
eu vi que o log na base dois de dois milhões é 20 vírgula nove.
Então, portanto, com menos de 21 iterações
do while a gente vai conseguir chegar qualquer elemento da lista telefônica ou
eventualmente dizer que a tal pessoa não está na lista telefônica.
Então a gente vai conseguir dar uma resposta menos de 21 milissegundos,
que é tempo muito bom.
O ser humano nem percebe 21 milissegundos de tão rápido.
Então a gente vê que diferentes algoritmos aí têm uma complexidade
diferente e isso é muito importante na hora de escolher algoritmo.
Então a conclusão a que a gente chega é que a busca binária é
algoritmo bastante eficiente.
Por isso ele é muito usado aí computação para encontrar coisas, fazer buscas.
Particular, ao estudar a eficiência de algoritmo é interessante a gente ver duas
coisas: a gente analisar a complexidade computacional de forma matemática desse
algoritmo e também realizar experimentos medindo o desempenho.
Então fica aí uma lição para você: pega uma lista bem grande, uma lista de cem mil
elementos ou milhão de elementos e faz uma busca sequencial, mede o tempo que demora,
e faz uma busca binária, mede o tempo que demora, Então é isso.
[MÚSICA]
[MÚSICA]
[MÚSICA]
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
