Como implementar BUSCA BINÁRIA? *Você deveria aprender isso!* | Algoritmos #10

há pessoal seu alisson e só com uma programação dinâmica do vídeo de hoje nós vamos estudar um algoritmo incrível chamado busca binário que vai permitir que este encontro um dado específico dentro de uma lista ordenada de uma maneira muito rápida se você acabou de chegar do canal já se inscreve fique com a gente que aqui além de aprender a programar ou se aperfeiçoar seu poder fazer um projeto muito interessante comigo ou com a 15 no dia anterior outro uma provocação para você a partir da pergunta quanto é que vale uma busca eficiente se você não

conferiu não deixe de ver porque com certeza vai valorizar ainda mais o o ritmo de hoje a busca binário depois de fazer reflexão que a gente fez aqui vídeo antes de colocá-lo no código implementará o ritmo vamos lá o quadro a gente entender como é que funciona então a gente tem uma lista que já está ordenada então é pressuposto do da busca binário que você vai operar essa o ritmo dentro de uma lista que está ordenada a mas a minha lista não está condenado ainda então você vai e roda algum houve condenação a gente viu

cinco aqui no bo sorte selection sorte em seu show sorte mande sorte o que sorte escolhe um roda na sua lista e depois se tiver ordenada pode rodar busca binário alienação já tem uma complexidade maior do que a busca mas você vai ver que se você for fazer essa busca vai às vezes vai compensar você fazer ordenação antes para depois poder fazer uma busca muito mais rápido tá bom toque a gente tem a lista ordenada 2 2 4 7 11 e 21 23 30 41 tá pode ter número repetido não tem nenhum problema a idéia

da busca binária é muito simples mas há sim muito poderosa é o seguinte você vai chegar e vai dividir essa lista no meio taça vai olhar porque está no meio e você vai perguntar se ele é um cara que você quer encontrar vamos supor que eu cheguei a encontrar aqui o número 30 tá então se eu fosse fazer uma busca e mear eu tenho que passar por todo mundo aqui desde os dois até chegar na penúltima posição ao i o 30 mas agora a fazer a busca minar vamos ver como é que a gente encontra

ele então a gente vai vim no cargo está no meio da lista em que é isso se você olhar essa lista tem nove posições tá tá vendo o índice zero até o índice 8 aquino 41 e aí para encontrar metade você soma então o índice inicial mas o índice final e 10 18 e dividir por dois anos e obter o índice 4 é a metade dessa sua lista você vem aqui 01234 daqui em cima do onze está a essa pergunta 11 é igual 30 que estou procurando não não é mas aí já que ele não

é que eu vou fazer o 30 ele está à esquerda ou à direita do onze então só posso responder essa pergunta com precisão é com a resposta correta se ela tiver ordenado ea polícia que é um pressuposto da busca bem na área é um dado que a lista ordenada eu sei que esse 11 é menor do que o número que eu tô procurando o 3130 está à direita dodô 11 e é isso me permite ignorar todos os elementos que estão a esquerda então a gente foi de atuar no meio ea gente vai ignorar todos os

que estão esquerda vai chegar vai olhar agora uma nova lista só com esses números aqui do onze até 1 41 tá certo e água a gente vai repetir o mesmo processo como se aqui fosse a nossa lista inicial então nessa lista aqui de 11 41 ante o olhar a praia do meio quem que é aqui agora é o 23 23 é igual a 30 não não é então o que a gente faz perguntas e 20 ou 30 do lado esquerdo o lado direito 23 sabendo que está condenado a gente verifica que o 30 no lado

direito do 23 também nos permite ignorar o 21 aqui é que tá esquerdo 23 e agora a nossa nova lista então que vai ser composta apenas por esses caras aqui ó 30 e 41 e aí dependendo de como você fizer a conta você vai acabar escolhendo um outro se você escolheu 30 34 30 você encontrou mesa já deu a resposta certa se acabou escolhendo 41 se vai repetir o procedimento mais uma vez e vai cair depois de uma pequena lista que tem só 30 e você encontra então essa ideia base da busca binária ea idéia

é que a gente vai replicar no código mas só assim a mais esse o elemento não estiver na lista então fazer uma nova busca que agora com um elemento que não está na lista por exemplo o número 1 tá então a gente tem 22 ali em 22 e não tenho um como é que a gente faria essa música então novamente começa pelo caso em meio a gente olha aqui 1111 não é um certo mas a gente sabe que o luta esquerda do onze porque está ordenado e uma menor do que o 11 então a gente

tem uma nova lista aqui que vai ser 2 até os 7 que a gente faz repete o procedimento aqui nessa lista pega o caminho do meio dependendo de como a gente fizer a conta vai cair nesse 2 ou no 4 elas implementação vai privilegiar que o 2 a 2 ele é maior do que um é diferente nosso um é maior do que o 1 então este pressupõe que um está à esquerda dois e aí ficamos então com este pequeno pedacinho é que tá essa aqui passa a ser a nossa lista agora e ela tem apenas

um elemento é esse elemento não é um então você vai acompanhar dois é diferente de um e vai ver que não tem mais como você reduzirá sua vista e você pode responder com certeza que não está nessa lista então o procedimento é o mesmo independente do nome está na lista ou não o dem ser repetido não tá se estivesse procurando dois a gente encontrar os dois aqui pode ser que em algumas implementações se encontra o 1o 2o o último dois enfim isso vai variar dependendo de como você escreva o seu código mas o fato é

que você sempre vai encontrar um nome eu sempre é poder dizer que ele não está lá tranquilo e aqui novamente lembrando que estão utilizando números números inteiros para facilitar a compreensão mas você pode utilizar isso em qualquer tipo de dado que você consiga realizar comparações tá então por exemplo estranhos é texto você poderia aplicar esse algoritmo desde que você realizou comparação teve uma história nada lá e depois pode comparar novamente para buscar tá bom então sabendo agora a ideia mais nada' busca minar elas faltam duas coisas a primeira delas é realizar a implementação do código

ea segunda é verificar a complexidade do algoritmo nós vamos aproveitar que já estão aqui no quadro para matar logo a partida complexidade porque vai ajudar visualmente a gente entender o que está acontecendo depois então a gente faz a implementação que vai ver que é tranquilo minha então voltou aqui o quadro eu coloquei destacadas assobios que nós analisamos para que você possa entender quantos passos foram executados e aqui estou focando no caso em que a gente procurou pelo número um porque o pior caso da música binária acontece quando você tenta com há um número não tenta

encontrar um elemento e você não encontra ele certo nesse segmento não está presente na lista você tem o pior caso da busca binária e nós vamos analisar a complexidade do pior caso quando ele tentou encontrar um que aconteceu primeiramente olhou né aqui o passo 10 é olhar para a lista que está em branco mesmo entrou para lista completa e fomos então em cima do onze tá depois que foi em cima do morro que é diferente do 1 a gente teve uma subida lista que é os elementos que estão esquerdo 11 então essa súbita que está

aqui em amarelo mesmo aí depois disso a gente desceu consumista que está aqui em roxo que tem só esse 22 depois de ser uma súbita que está em vermelho e finalmente pode é falar é categoricamente que um não se encontra na lista porque a gente olhou até ter um único elemento da lista para poder analisar não poder mais reduzir a nossa lista mesmo quantos passos aconteceu aqui você pode olhar e ver que teve quatro passos mas como é que se pode obter uma expressão que diz assim tá pra determinar o tamanho da lei esta gente

sempre vai ter x paços está sem contar que está acontecendo o seguinte você sempre está reduzindo a sua lista pela metade então inicialmente você tinha nove elementos depois passou a ter quatro elementos depois dois e depois um então sempre vai acabar tendo um único elemento aguentar quando você não encontra esse cara na lista o pior caso vai ser se você teve um único elemento lá no final e nem manoel carlos não encontrou então o pior caso sempre vai terminar tendo um único elemento e sempre vai decrescer / 2 o tamanho da sua lista então a

minha lista ela tinha mil e 24 elementos ainda dividiu você vai para um lado com 512 o outro lado ficou em 11 12 para lá a dirigir de novo 256 de 1928 64 32 16 8 421 beleza ao jornal que não vão ser redondinhas assim há divisões exatas sempre tal mas aproximadamente vai ser isso você vai estar dividindo a quantidade de elementos que você tem por dois até que você fique com um único movimento lá e posso dizer que caia não tá tudo bem então você tem que notar isso você consegue entender a complexidade da

busca binária por quê o que essa idéia de dividir sempre pelo mesmo número ali ela é intrinsecamente ou o marítimo tá então não é muito caro para muita gente isso às vezes as pessoas são um pouco confuso em relação ao marítimo mas elas têm mais facilidade de entender potenciação por exemplo então quando não está multiplicando direto por dois você diz que você tem dois eu invado a quantidade de vezes que você multiplicou essa potenciação certo então dois elevada 2 é dois meses dois têm 22 ainda é um do lado do outro foi levado a 32

meses dois meses dois de novo sentei 32 ale em 2003 é 8 tá e se você fizer o inverso né o gari timo de 8 na base dois você obter exatamente 3 então é quantas vezes você consegue dividir o 8 e por dois estão voltando isso fica muito fácil você perceber que a complexidade da busca binária ela vai ser o grande de logaritmo tá dn em que n é o tamanho da sua entrada da sua lista e então a vai ser exatamente o iene não se você olhar aqui por exemplo a gente tem nove né

9 mais aproximado epílogo de 2018 e óleo de 8 na base de kaboul dever que é três vezes sabendo que está fazendo aqui um passo em branco 2 em v e amarelo 3 em roxo 4 em vermelho tá então na verdade este blog e mais um tá mas você pode é quando passar a notação do grande e se alguém mais um e se mais não cortasse a ficar apenas com uma coisa que é o ambiente é importante saber que é proporcional ao organismo dn falassem por mais essa escreveu sua obra especificando que a base e

dois bombons dança de base no ritmo é essencialmente multiplicação de uma constante ea gente já viu que a notação do grande ela e mim essa constante que importa pra gente saber realmente qual que é a base da função ali o h1n1 então você sabe que o blog de a na base b é igual o lobby de anabazys e / logo db na bases e também que a gente possa informação e sabendo a complexidade da busca binário a gente pode realizar uma comparação muito interessante com caso que eu te dei no vídeo anterior então eu comentei

no vídeo anterior que você podia ter uma lista com 10 milhões de elementos que queria realizar uma busca por um evento aqui dentro não é um dado específico e no pior caso você tenha que passar por todos os 10 milhões e poderia se fizesse uma busca linear que tivesse que começar pelo começo mesmo teto o índice 0 e poderia estar no último índice você passou então por 10 milhões de elementos isso te daria mais ou menos 10 segundos fazendo um bilhão de operações por segundo e agora com a bucha binária você sabe que você consegue

fazer uma coisa de passos proporcional à log de 2 bilhões certo e aí aplicando essa propriedade que a gente viu né 10 milhões e 10 elevado a 10 e aí a gente tem que lobby de 10 milhões estão nas 10 elevado a 10 na base 10 é igual ao longo de 10 bilhões na base 2 que é quem está interessado se quiser ser mais rigoroso dividido pelo aumento de 10 na base dois então o óleo de 10 milhões na base dois é igual a 10 nec é obra de deus base 10 ou dez vezes o

óleo de 10 na base dois longas de abbas e dois é algo entre 3 e 4 mais próximo do 3 está então você pode chutar para mais 6 a 4 e isso vai ver que então um número de passos que vai realizar para encontrar um elemento dentro de uma lista de 10 milhões de elementos é menor do que 40 então assim é muito rápido você fizer um bilhão de operações por segundo por 40 é muito rápido mesmo tá então a buscar mizael ritmo muito eficiente mas só funciona com as hipóteses de que saulo está ordenada

então a gente já sabe a teoria da bobina vão fazer a implementação desse negócio então aqui eu criei um novo arquivo é o que eu chamo de sorte ponto pai ea gente vai definir então uma nova função chamar que death de baile online search busca minar em inglês ea gente vai precisar passar como argumento o seguinte bom a lista que a gente quer buscar que o chamará que dê a rejeitar não vou chamar de início porque este é uma função aqui no país e você precisa minimamente twitter em que você quer buscar também tá uma

coisa interessante é que a gente vai utilizar uma estratégia recursiva nessa solução aqui tá se você quiser eu faço uma solução equitativa depois deixe nos comentários a gente pode fazer também mas a gente vai fazer essa primeira solução como uma solução recursiva então para controlar onde que eu comece onde que eu termino né ali dentro da lista dessas subiu estudos a gente vai precisar do índice de começo que eu chamaria de bim e doença de fink o chamado the end tá bom a gente já utilizou esse tipo de estratégia por exemplo mais de sorte do

que sorte está usando aqui mais uma vez no bairro set e aí a gente vai fazer a seguinte verificação se o começo tem for menor ou igual ao fim então eu tenho uma súbita válida né eu vou a calcular o meio dela tá então o meio vai ser igual ao começo mas o fim / 2 ea gente vai utilizar duas barras para dividir porque vai dar respaldo à divisão inteira pra gente em python tá e aí o cálculo esse meio e eu vou verificar se o cara que está no meio né cara nessa posição aqui

será igual ao cargo estou procurando é esse item que está sendo procurado então se eu for igual encontrei eu posso retornar o índice m é o índice do meio ora encontrei ele está nessa posição aí sim não foi igual aí eu vou verificar se ele é menor tá bom então se ele for menor vamos ver que esse item foi menor do que o canal do meio então eu vou pela esquerda então pedi para retornar por resultado da busca binária é no mesmo rei tá o mesmo conjunto de dados é buscando pelo mesmo item beleza é

mantendo o mesmo começo porém o fim água e vai ser igual à metade no caso da metade - muito não preciso passar metade mesmo porque já sei que é diferente eu posso empurra uma posição ali pra esquerda então tô passando ali a subir esta esquerda para ser buscado e caso contrário é caso item seja maior do que o kaká no meio então vou pedir para retornar fazer o mesmo esquema que retornar o resultado da busca binária sobre o mesmo reinés mesmo conjunto de dados com o mesmo elemento sendo buscado só que agora eu vou modificar

o começo o começo e vai ser o primeiro carro que está à direita do meio e um fim ele se mantém tá bom e caso contrário né se não tiver uma submissa vale do lecce o filme por exemplo for menor do que o começo ao retornar nome porque a nossa representação do nada do brasil tá de uma joint inválido teve que perguntar se por mais que não pode retornar será menos um por exemplo é que poderia ser um inválido no python - um homem se valido do python -1 e representa o último índice é você

pode utilizar índices negativos só vai à lista de trás pra frente por isso quem está retornando aqui o nome que é uma coisa especial em particular se a gente deixar do jeito que está necessariamente quando for rodar ele nessa eu tiver uma lista que esse lado isto é igual a 2 3 e 4 eu vou ter que chamar baile sorte passando a lista dizendo que encontrasse ao número 4 e eu vou ter que especificar que 0 e esse lá tamanho da lista menos né porque o índice barulho então eu não quero fazer isso na primeira

vez que o que foi chamado a função é quando foi chamar a função procurar na lista inteira eu quero chamar ela dessa maneira aqui só passando a lista que vai ser procurado o elemento que vai encontrar tá bom então pra que eu possa fazer isso eu tenho que dar valores padrões aqui né o valor padrão para cada um desses argumentos aqui então bin o padrão é começar com 10 e pro and infelizmente não consigo chamar função lenk ali no argumento então vou passar aqui também o nome e ele vai fazer uma verificação aqui se esse

and ele é nome se for bom né aí a gente diz que o end é igual tamanho da lista no caso da verdade a rei nossa variável - um porque eu quero que seja um índice válido tá bom então com isso aqui a gente fecha tá nossa busca binária noite precisa testar esse é o último estudo a funcionando e eu já tenho um arquivo de teste aqui tá todos os dois arquivos tanto a implementação da busca mina é quando esse arquivo de testes vão poder encontrar aqui na descrição do vídeo um link la politique hobby

que vai ter tranquilidade e se aquilo de teste eu fiz alguns como em alguns testes já previamente aqui pra gente o primeiro é uma lista vazia tá então nada mais você não pode encontrar o alimento obviamente se que em turno único é uma luta que tem um único elemento tá uma lista com dois elementos e aí depois aí os casos são similares né então tem uma lista que tem um número ímpar de elementos uma vez que têm um número par de elementos só pra você ver que funciona aquela divisão com os dois casos e aqui

uma lista que tem alimento e os repetidos então se não passar no teste vazio vai dizer aqui o que falhou se não passar no teste unitário também vai dizer que falhou se passava dizer que passou e nos outros a gente vai ter oportunidade de selecionar algum elemento que vai poder falar o nome do guia e procura e disse tá ou não qualquer o índice é nome esse tipo de coisa a gente pode ficar repetindo algumas vezes esses teste então depois pode dar uma olhadinha com calma pra entender esse código aqui nenhum bicho de sete cabeças

qualquer dúvida bota aí na descrição do vídeo então vamos lá vão rodar que python 3 teste ponto pai ea gente passou no teste vazio passou no teste único também talvez fique se perguntando mas a gente não fez esse teste em relação ao vazio mas como a gente a gente começa aqui com o emd igual ao tamanho do rei - 1 se o tamanho do reforço 0 né é tá base no tamanho da reserva ainda o índice que vai ser menos um e aí como o começo está em zero e o final time - um isso

aqui não vai ser verdade né este é um caso que a gente tenha subido isso invalida a gente tem o final menor do que o começo e aí naturalmente passa pra cá e retorna o nome diz que não encontrou então já está contemplado nesse caso de de teste dentro da nossa implementação aí pro caso de testes de dupla a gente pode testar a escolha por exemplo 3 tá e aí diz então que o trecho 2001 ótimo o caso de teste inpa vamos testar aqui com o 27 ele diz que está no índice 8 ea gente

mas com taxa de 0 1 2 3 4 5 6 7 8 de fato 27 o paa a gente vai botar lá 3 está no índice 2 de fato ele está aqui no índice 2 o cara que tem número repetido não botar sei lá 21 bom certamente 21 à noite está em bairros isso aqui também pode repetir vou repetir vou procurar aqui na dupla por exemplo agora sei lá 8 e aí ele disse que não encontrou seu procurar aqui no inpa hum vamos ver um encontro aqui no índice zero no país e pode procurar por

alguma coisa que não está aqui não encontrou no repetido posso procurar também por lá 9 que a união está repetindo ea gente então onde estão esses 60 123456 fato tá então finalmente nós temos uma implementação funcionando na nossa busca binária você pode baixar esse código estudar e fazer seus próprios testes tão pessoal esse vídeo ficando por aqui pra você tenha entendido a idéia é incrível por trás da busca binária e também tem aprendido a implementar esse algoritmo se você gostou do vídeo mas quero deixar o celular que não se inscreveram no canal para dar aquele

apoio ao trabalho estamos com a meta de bater 5 mil inscritos até o final do ano então se você acredita no nosso trabalho ajude a compartilhar favor muito obrigado e até a próxima