[Música tocando] 

DOUG LLOYD: Tudo bem. Então, é uma busca binária algoritmo podemos usar para encontrar um elemento dentro de uma matriz. Ao contrário de busca linear, requer um condição especial ser atendidas previamente, mas é muito mais eficiente se essa condição é, de facto, cumpridos. 

Então, qual é a idéia aqui? é dividir e conquistar. Queremos reduzir o tamanho da a área de pesquisa para metade de cada vez a fim de encontrar um número de destino. Este é o lugar onde essa condição entra em jogo, no entanto. Nós só pode alavancar o poder de eliminando metade dos elementos sem sequer olhar para -los se a matriz está classificada. 

Se for uma mistura completa-se, Não podemos simplesmente fora de mão descartar metade dos elementos, porque não sabemos o que estamos descartando. Mas, se a matriz é classificada, nós podemos fazer isso, porque nós sei que tudo ao deixou de onde estamos atualmente deve ser inferior a valor que estamos atualmente. E tudo para o certo de onde estamos deve ser maior do que o valor atualmente estamos olhando. 

Então, qual é o pseudocódigo passos para a pesquisa binária? Nós repetimos este processo até que o matriz ou, à medida que prosseguimos através, matrizes sub, pequenos pedaços de a matriz original, é de tamanho 0. Calcular o ponto médio do sub matriz atual. 

Se o valor que você está procurando em que elemento da matriz, pare. Vc achou. Isso é ótimo. Caso contrário, se o destino for menos do que o que está no meio, por isso, se o valor que estamos procurando para é menor do que o que vemos, repetir esse processo novamente, mas alterar o ponto final, em vez de ser o original completar gama completa, para ser apenas para a esquerda de onde nós apenas olhou. 

Sabíamos que o meio era muito alto, ou o alvo era menos do que a média, e por isso deve existir, se ela existe de todo na matriz, um lugar para a esquerda do ponto médio. E por isso vamos definir a matriz localização, apenas à esquerda do ponto médio como o novo ponto final. Por outro lado, se o destino for maior do que o que está no meio, fazemos exatamente o mesmo processo, mas em vez disso, alterar o ponto de início para ser apenas para a direita do ponto médio nós apenas calculado. E então, começamos o processo novamente. 

Vamos visualizar isso, OK? Portanto, há muita coisa acontecendo e aqui, mas aqui está uma matriz de 15 elementos. E nós estamos indo para ser manter o controle de muito mais coisas neste momento. Assim, em busca linear, fomos apenas se preocupar com um alvo. Mas desta vez queremos se preocupam com onde estamos começando a olhar, onde que estamos parando olhando, e qual é o ponto médio da matriz atual. Então, vamos lá com busca binária. Estamos praticamente pronto para ir, certo? Eu só vou colocar para baixo abaixo aqui um conjunto de índices. Esta é, basicamente, apenas o elemento da matriz que estamos falando. Com a busca linear, nós cuidado, na medida em que precisa saber quantas elementos que estamos iterando, mas nós realmente não ligo para o que elemento que está olhando. Em busca binária, o que fazemos. E assim esses são apenas lá como um pequeno guia. 

Assim, podemos começar, certo? Bem, não exatamente. Lembre-se que eu disse cerca de busca binária? Não podemos fazê-lo em um matriz não triados ou mais, que não são garantindo que o certos elementos ou valores não são sendo acidentalmente descartados quando nós apenas decidir ignorar metade da matriz. 

Então, passo um com pesquisa binária é que você deve ter uma matriz classificada. E você pode usar qualquer um dos triagem algoritmos que falamos para chegar a essa posição. Então, agora, estamos em uma posição onde podemos executar a busca binária. 

Então, vamos repetir o processo passo a passo e manter a par do que está acontecendo à medida que avançamos. Assim, o primeiro que precisamos fazer é calcular o ponto médio da gama corrente. Bem, vamos dizer que estamos, em primeiro lugar tudo, olhando para o valor 19. Nós estamos tentando encontrar o número 19. O primeiro elemento do presente matriz está localizada no índice zero, e o último elemento da presente matriz está localizada no índice 14. E por isso vamos chamar aqueles início e fim. 

Então nós calculamos o ponto médio por adição de 0, mais 14 dividido por 2; ponto médio bastante simples. E podemos dizer que o ponto médio é agora 7. Assim, é de 15 o que estamos procurando? Não é não. Estamos à procura de 19. Mas sabemos que 19 é maior do que o que nós no meio. 

Então, o que nós podemos fazer é alterar o ponto de início ser apenas para a direita da ponto médio, e repita o processo novamente. E quando fazemos isso, nós agora dizem que a novo ponto de partida é a localização matriz 8. O que temos feito é eficaz ignorado tudo para a esquerda de 15. Nós eliminamos metade do problema, e agora, em vez de ter que procurar mais de 15 elementos em nossa matriz, só temos que procurar mais de 7. Então 8 é o novo ponto de partida. 14 ainda é o ponto final. 

E agora, nós vamos sobre isso novamente. Nós calculamos o novo ponto médio. 8 mais 14 é 22, dividido por 2 é de 11. É isso que estamos procurando? Não é não. Estamos à procura de um valor que é menos do que o que acabou de encontrar. Então, nós estamos indo para repetir o processo novamente. Nós vamos mudar o ponto final para ser apenas para a esquerda do ponto médio. Assim, o novo ponto final torna-se 10. E agora, que é a única parte do a matriz temos que classificar completamente. Portanto, temos agora eliminado 12 dos 15 elementos. Sabemos que, se 19 existe na matriz, ele deve existir algum lugar entre o elemento número 8 e elemento de número 10. 

Então nós calculamos o novo ponto central novamente. 8 acrescido de 10 é 18, dividido por 2 é 9. E, neste caso, olha, o alvo está no meio. Encontramos exatamente o que estamos procurando. Nós podemos parar. Nós concluído com êxito uma pesquisa binária. Tudo certo. Então, nós sabemos que este algoritmo funciona se o alvo é algures no interior da matriz. Será que este algoritmo de trabalho se o alvo não está na matriz? Bem, vamos iniciá-lo novamente, e desta vez, vamos olhar para o elemento 16, que visualmente podemos ver não existe em qualquer lugar na matriz. 

O ponto de partida é novamente 0. O ponto final é novamente 14. Esses são os índices da primeira e últimos elementos da matriz completa. E nós vamos passar pelo processo que acabamos passou por mais uma vez, tentando encontrar 16, embora visualmente, já podemos dizer que não vai estar lá. Nós apenas queremos ter certeza este algoritmo será, de fato, continuam a trabalhar de alguma forma e não apenas deixar-nos preso em um loop infinito. 

Então, qual é o primeiro passo? Calcular o ponto médio da matriz atual. Qual é o ponto médio da matriz atual? Bem, é 7, certo? 14 mais 0 dividido por 2 a 7. 15 é o que estamos procurando? Não. É muito perto, mas nós estamos olhando para um valor um pouco maior do que isso. 

Então, nós sabemos que ele vai estar em lugar nenhum à esquerda de 15. O alvo é maior do que o que está no ponto médio. E, assim, definir o novo ponto de partida para ser apenas para a direita de meio. O ponto médio é actualmente 7, assim digamos que o novo ponto de partida é 8. E o que nós temos efetivamente feito de novo é ignorado toda a metade esquerda da matriz. 

Agora, nós repetimos o processar mais uma vez. Calcular o novo ponto médio. 8 mais 14 é 22, dividido por 2 é de 11. 23 é o que estamos procurando? Infelizmente não. Estamos à procura de um valor que é inferior a 23. E assim, neste caso, nós vamos para mudar o ponto final para ser apenas para a esquerda do ponto médio do curso. O ponto médio de corrente é de 11, e por isso vamos definir o novo ponto final para a próxima vez que vamos por este processo a 10. 

Novamente, nós passar pelo processo novamente. Calcular o ponto médio. 8 mais 10 dividido por 2 é 9. 19 é o que estamos procurando? Infelizmente não. Nós ainda estamos procurando um número menor do que isso. Então, nós vamos mudar o ponto final neste momento ser apenas para a esquerda do ponto médio. O ponto médio é actualmente 9, de modo que o ponto final será 8. E agora, estamos apenas à procura a matriz de um único elemento. 

Qual é o ponto médio dessa matriz? Bem, começa às 8, ele termina em 8, o ponto médio é de 8. É isso o que estamos procurando? Estamos à procura de 17? Não, nós estamos olhando para 16. Portanto, se ela existe na matriz, ele deve existir algum lugar para a esquerda de onde estamos atualmente. Então, o que vamos fazer? Bem, vamos definir o ponto final para ser apenas para a esquerda do ponto médio do curso. Então, nós vamos mudar o ponto final a 7. Você vê o que apenas aconteceu aqui, embora? Olhe aqui em cima agora. 

Iniciar agora é maior que final. Efetivamente, as duas extremidades da nossa matriz ter cruzado, e é o ponto de partida Agora, após o ponto final. Bem, isso não faz faz qualquer sentido, certo? Então, agora, o que podemos dizer é que tem um sub matriz de tamanho 0. E uma vez que estamos chegado a Neste ponto, podemos agora garantir que elemento 16 não existe na matriz, porque o ponto de partida e ponto final cruzaram. E assim ele não está lá. Agora, observe que este é ligeiramente diferente do que o ponto inicial e final apontar sendo o mesmo. Se tivéssemos sido à procura para 17, teria sido na matriz, e o ponto de início e ponto final dessa última iteração antes desses pontos cruzados, que teria encontrado 17 lá. É só quando eles cruzam o que pudermos garantir que o elemento não faz existem na matriz. 

Então, vamos ter um monte menos etapas do que busca linear. No pior caso, tivemos para dividir uma lista de n elementos repetidamente ao meio para encontrar o alvo, quer porque o elemento alvo vai estar em algum lugar no último divisão, ou ele não existe em tudo. Então, na pior das hipóteses, temos que dividir os array-- você sabe? Log de n vezes; nós tem que cortar o problema em metade de um certo número de vezes. Esse número de vezes que é log n. 

Qual é o melhor cenário? Bem, a primeira vez que calcular o ponto médio, encontramos o que estamos procurando. Em toda a anterior exemplos de busca binária nós apenas ido mais, se tivéssemos está procurando o elemento 15, que teria encontrado que imediatamente. Isso foi no início. Esse foi o ponto médio de a primeira tentativa de uma cisão de uma divisão na busca binária. 

E assim, no pior caso, busca binária é executado no registo n, o qual é substancialmente melhor que busca linear, no pior dos casos. No melhor dos casos, binário busca é executado em omega de 1. Assim, busca binária é muito melhor do que a busca linear, mas você tem que lidar com o processo de classificando sua matriz antes de se poder alavancar o poder de busca binária. 

Eu sou Doug Lloyd. Este é CS 50.