[MÚSICA] Olá, vamos conversar pouco sobre tipo de algoritmo que é muito utilizado computação. Que é o algoritmo de busca. Existem diferentes jeitos de fazer buscas e a gente vai ver alguns desses jeitos aqui. Vamos começar pelo jeito mais simples e depois sofisticar pouquinho. Vamos supor que você tem uma sequência de números, do tipo float, que você quer encontrar nessa sequência, nessa lista, uma lista de números se determinado número que você está procurando, está dentro dessa sequência. E a gente, no mundo real, essa é uma coisa que a gente faz muito, por exemplo, numa biblioteca vai ter banco de dados ali, a gente pode enxergar a biblioteca como uma sequência enorme de livros, a gente vai querer buscar determinado livro ali dentro. Ou, se tem uma lista de alunos de uma determinada disciplina, a gente quer saber se determinado aluno com determinado código ou determinado nome está matriculado naquela disciplina, a gente tem que percorrer a lista de alunos e encontrar. Uma lista telefônica, por exemplo, a gente tem a lista de telefones de uma determinada cidade, a gente quer achar o telefone de uma pessoa, então a gente tem que percorrer a lista buscando qual é o telefone de uma pessoa com determinado nome. Então, tem dezenas, centenas de exemplos no mundo real que a gente usa sistemas de software para fazer buscas, então eu preciso de algoritmo de busca para encontrar coisas. O algoritmo mais simples que a gente pode imaginar é o que a gente chama de busca sequencial, que é o que a gente está vendo aqui. Então como funciona essa busca sequencial? A gente vai sequencialmente, desde o primeiro elemento da lista até o último elemento da lista, verificando se aquilo que a gente está buscando é cada elemento da lista. Então a gente tem uma variável i ali, que a gente chama de índice que vai percorrendo os elementos da lista e a cada interação a gente vê se o elemento que está na posição i da lista é igual ao elemento que a gente está procurando. Então, nesse caso, a busca sequencial recebe dois parâmetros: a sequência na qual a gente está fazendo essa busca, essa lista de elementos, e a gente está buscando número x. Aqui tem comentário que está dizendo quais são os tipos aqui que são passados como parâmetros. É passado algo do tipo lista, list. E depois número do tipo float. E o quê que a função devolve? Essa função vai devolver valor booleano. Vai ser verdadeiro ou falso. Ou seja, verdadeiro se encontrou o elemento na lista e falso se não encontrou o elemento na lista, tá. Como que a gente faz isso, então? É muito simples. A gente faz for para percorrer todos os elementos, esse for vai ter uma variável in, nesse índice e que elementos que ele vai percorrer, desde o zero até o comprimento da sequência menos. Como que a gente fazer isso? Usando-se o range que a gente já viu. Range, lenght que é o comprimento da sequência, ele vai de zero até o comprimento da sequência menos. O i vai de um: zero, dois, três, quatro, cinco até chegar no comprimento da sequência menos. E daí para cada interação do for, o que a gente faz? Se o elemento que está na posição i dessa sequência for igual ao elemento x que é o float que a gente está procurando, se a gente encontrou o elemento, aí você devolve o verdadeiro. Caso contrário, o que você faz? Você vai para próxima interação do for, então, você vai percorrendo todos os elementos e algum momento ali, entre o zero e o comprimento de sequência menos se encontrar o elemento x algum elemento, daí a gente já sai dessa busca sequencial devolvendo o true. Return true, quando chega no return ele sai imediatamente da busca e volta para quem chamou a busca, executou essa função busca. Agora, se por algum, se por acaso esse if nunca é executado, quando que o if nunca é executado? Quando o elemento x não está na lista. Se o elemento x não aparece na lista esse if aqui, esse comando do if nunca vai ser executado. Então, esse return true nunca vai ser executado, o for vai chegar até o seu final, ele vai executar para o último elemento não vai encontrar e vai para o próximo, mas depois do último o quê é que ele faz? Ele termina o for e vai para a próxima linha. Daí o que diz a próxima linha? A próxima linha diz return false. Então, caso a gente não encontre o elemento na lista, ele devolve falso. Então, essa é uma implementação muito simples de uma busca sequencial. Vamos ver mais uma implementação aqui, pouquinho mais sofisticada, que eu implementei antes aqui. De uma busca sequencial também e eu fiz exemplo pouco mais divertido. Como eu adoro música eu fiz exemplo musical, envolvendo playlists. Eu quero buscar uma música dentro de uma playlist. Então, o que é uma playlist? Uma playlist é uma sequência de músicas. E eu fiz aqui uma sequência, uma lista, de objetos do tipo música. Então, eu criei uma classe chamada música e eu criei o construtor dessa classe chamada música. Então, o quê é que você tem que passar como parâmetro no construtor? Você passa o título da música, o nome do intérprete, o nome do compositor e o ano que a música foi gravada. E essas variáveis título, intérprete, compositor e ano, ele guarda atributos do objeto que está sendo instanciado, do objeto que está sendo criado. Então, dessa forma, com essa classe música aqui, a gente pode criar novas músicas armazenando todas essas informações sobre cada música. E daí uma playlist vai ser uma lista, uma sequência de músicas. Daí, eu criei para exemplificar aqui, essa classe buscador. A classe buscador, ela tem dois métodos, primeiro método busca por título, que recebe como parâmetro aqui primeiro self, que é o próprio interpretador que passa, depois ela recebe uma determinada sequência, que essa sequência aqui, na verdade, vai ser a playlist, que eu vou passar como parâmetro ali, e determinado x. Quem é o x? O x vai ser o nome de uma música, o título de uma música que eu estou buscando. E daí a implementação é muito simples. É o que gente viu antes. Tem o for aqui, que vai percorrer todos os elementos dessa sequência e aqui tem uma pequena mudança, que eu estou comparando com determinado atributo, então eu faço se seq [i]. título. Ou seja, se o título da música que está no índice i for igual a x. Que é o que foi passado ali como parâmetro como título. Daí, devolva, e aqui outra mudança. Não estou devolvendo verdadeiro ou falso. Estou devolvendo o índice no qual eu encontrei o elemento. Então, se seq [i]. título = x, eu devolvo esse índice i. E se eu chego até o final e não encontrei nenhum elemento, aquela música que eu estou buscando, eu dou return menos para indicar, é índice que não faz sentido, né, é índice antes do começo. Então, ele vai ser menos para indicar que não encontrou a música na lista. Na verdade, vez de x aqui acho que eu vou colocar o título. Fica mais claro. Sempre a gente é bom buscar nomes muito claros para as nossas variáveis. X não quer dizer nada. E talvez aqui a gente pode até chamar de playlist. Então, aqui, sempre que você encontrar uma oportunidade para tornar o seu código mais claro não deixe para depois. Você imediatamente já melhora a qualidade do seu código. Pronto, já fizemos isso aqui. Então, esse aqui é o método busca_por_título. Agora, aqui tem exemplo de uso desse método busca_por_título. É método que eu chamei de vamos_buscar. O quê que eu faço nesse método? A primeira coisa que eu faço, eu crio uma playlist bem simplesinha com três músicas. Então, na verdade, o quê que eu fiz aqui? Note que aqui tem o abre colchetes e aqui eu fecho colchetes. Então, isso aqui é uma lista e essa lista tem três elementos que são, na verdade, três músicas. Então, o que eu estou fazendo aqui, eu estou instanciando três vezes, objetos da classe música e cada vez passando como parâmetro valores diferentes para os seus atributos. Então, a primeira música é Ponta de Areia do Milton Nascimento, executada pelo Milton de 1975, música lindíssima. Depois Podres Poderes do Caetano Veloso de 1984, muito legal. E depois Baby, cantada pela Gal Costa, composta pelo Caetano Veloso. Se não me engano é de 1979, talvez esteja errado, é bom vocês verificarem se está certo esse ano aí que foi gravado pela Gal, essa música. E daí, então, criei a minha playlist, agora eu vou chamar aqui esse método busca_por_título. Como é método da minha própria classe, eu estou dentro da classe buscador. Eu faço self.busca_por_título. E daí eu passo como parâmetro, tem que passar aqui a playlist, título playlist, que é essa variável aqui playlist e o título, nesse exemplo eu estou buscando aquela música Baby. E daí, o quê que ele faz? Ele vai devolver o índice onde ele achou, se é que ele achou, né. Ele vai devolver o índice onde achou aquela música e eu guardei numa variável chamada onde_achou. Daí, o quê que eu faço? If onde achou é igual a menos daí significa que não encontrou, devolveu menos aqui, não encontrou música. Daí ele imprime "minha música preferida não está na playlist". É, se caso contrário, o quê que ele faz? Ele guarda essa variável preferida, playlist de onde achou. Ele pega o elemento que está na posição de onde achou do playlist e guarda nessa variável preferida e depois ele imprime aqui o título da preferida, o intérprete, o compositor e o ano separado por vírgulas. Então, vamos executar isso aqui? Então, inicialmente eu estou buscando o Baby aqui. Então deixa eu mandar, eu vou mandar executar. Primeira coisa, eu tenho que criar uma instância dessa classe buscador, então vou chamar de b. Então, pronto, a variável b agora é objeto do tipo buscador, ele é capaz de fazer buscar particular. Ele é capaz de executar esse método vamos_buscar. Então, aqui, vamos buscar. O quê que acontece quando eu executo esse método? Ele, lembra ele chamou Baby. Ele achou Baby da Gal Costa, interpretação da Gal, composição do Caetano de 1969. Se eu buscar aqui uma outra música, sei lá, Stairway to Heaven. Será que tem na minha playlist de músicas preferidas, essa aqui? Vamos ver. Vamos executar. Daí eu vou ter que executar, repetir esse comandos aqui, então, criar buscador e daí b vamos buscar ali o Stairway to Heaven. "Minha música preferida não está na playlist". Na verdade essa não é minha música preferida, mas é, por isso que ela não está na minha playlist. Mas esse aqui foi caso que ela devolveu menos. Então, aqui devia imprimir na verdade "A música buscada não está na playlist". A música buscada não está na playlist. Então, o que a gente viu aqui foi a busca sequencial, tá. Vamos agora, no próximo vídeo refletir pouco aí sobre se a busca sequencial é jeito eficiente ou não de se fazer buscas. [MÚSICA] [MÚSICA] [MÚSICA]
