[Powered by Google Translate] [Seção 3] [menos confortável] [Nate Hardison] [Harvard University] [Esta é CS50.] [CS50.TV] Tudo bem, vamos começar. Bem-vindo à Semana 4 da CS50. Se vocês abrir um navegador e abrir pset 3, Scramble com CS50, vamos começar a ir através da seção de perguntas lá. Assim como na semana passada, nós estaremos trabalhando no CS50 Spaces, se você também vai puxar que até bem, e se você vá em frente e visite este link que eu tenho aqui em cima no topo. É hora de começar. Nós temos o nosso programa oi pouco aqui. Nada louco. Uma das primeiras coisas que eu quero fazer com vocês hoje é passar por cima de algumas soluções ao Conjunto de Problemas 1, espécie de exemplos de soluções, só assim você pode ter uma idéia de que tipo de equipe código é escrito, que tipos de estudantes de código outros estão escrevendo, e ter que dar uma olhada nisso, porque eu sei que é estranho quando você enviar uma solução para um conjunto de problemas e obter comentários em sua própria versão, mas às vezes é útil para ver como as outras pessoas o fez, especialmente aqueles que são agradável. Para a maior parte, eu fiquei realmente impressionado com as soluções que vocês produziram. Eu ainda não comecei a olhar para os seus 2s conjunto de problemas, mas se for qualquer coisa como o primeiro, isso não significa nada além de coisas boas. Se você olhar para minhas revisões, vamos começar todo o caminho de Revisão 1, e vamos dar uma olhada rápida em uma solução Mario. Se você puxar isto, estes programas que vamos apresentar são corretas. Não houve problemas de regularidade com esses problemas, mas sim, queremos falar um pouco sobre as questões de design diferentes que estavam a ser usados ​​aqui. Uma das coisas que era interessante sobre a solução é que ele usou este novo conceito chamado de libra definir, por vezes também referido como um hash definir. Deixe-me ampliar-lo aqui. A # definir permite dar nomes a esses números em seu programa. Neste caso, a altura máxima de uma pirâmide em Mario foi de 23 e em vez de colocar 23 no meu código- que se referem a isso como codificação dura 23 - vez o que dá o nome max_height a esse número, de modo que aqui no meu loop do-while você pode realmente se referir a max_height em vez de colocar o número 23 polegadas [Estudante] Qual é a vantagem de fazer isso? Essa é uma grande questão. Uma delas é a legibilidade. Uma vantagem de usar este # define é a legibilidade. Quando eu estou lendo esse código, eu posso ver o que está acontecendo. Eu posso ver nessa condição aqui que estamos testando para a altura de ser <0, o que poderíamos ter definido também para ser de uma altura mínima ou uma altura min. A outra vantagem é que eu posso então ler o resto da linha para ver que está também a verificação para certificar-se que a altura não é maior do que a altura máxima, porque nós vamos continuar enquanto que a altura é maior que a altura máxima. A outra vantagem é, se eu diminuir o zoom um pouco aqui- se eu executar este programa e executá-lo, digamos, com 23, agora, ele irá imprimir todos os 23 linhas apenas como aquele. Mas dizer que eu queria mudar a altura máxima, e agora eu quero limitar a altura máxima das pirâmides para ser apenas dizer-homem, que foi descolados. # Include, # define max_height, e vamos dizer que queria defini-lo igual a 10. Agora, neste momento, tudo o que eu tinha a fazer era mudar isso neste local um. Eu posso recompilar o código, e agora se eu tentar digitar 12, ele vai me perguntar novamente. Neste caso, estamos apenas usando max_height uma vez. Não é que de um grande aborrecimento para ir em e alterá-lo no loop while se você precisar. Mas em programas onde você está referenciando o mesmo número mágico uma e outra vez, este # define mecanismo é realmente útil porque você simplesmente mudá-lo uma vez no topo do arquivo que é geralmente onde você colocá-los- e a mudança se infiltra através do resto do ficheiro. Outras coisas que eu queria observar nesta tarefa que eu achava que parecia muito bom, um era o nome das variáveis. Você vê aqui que temos variáveis ​​inteiras chamadas de linha e chamada altura. Espaços, hashes, que ajuda a tornar o código um pouco mais legível, torna um pouco mais compreensível o que está realmente acontecendo. Isto está em contraste com o uso, por exemplo, letras aleatórias ou apenas gobbledygook completamente. A última coisa que eu vou apontar é que, em loops, muitas vezes essas variáveis ​​iterador, estes contadores que você usa em seu loops, é padrão e convencionais para os iniciar com qualquer i e j em seguida, e, em seguida, k e ir de lá, se você precisa mais variáveis, e isso é apenas uma convenção. Há muitas convenções. Ele depende da linguagem de programação que você está usando. Mas em C, que normalmente começam com i. Não faz sentido usar, por exemplo, a ou b , dependendo da situação. Isso é tudo para este. Se agora você puxar para cima Revisão 2, você verá um outro Mario, e este é semelhante a outra que acabamos de ver, mas ele faz algo do tipo legal. Se olharmos para esta seção aqui no interior do interior para o laço, eles estão usando alguma sintaxe louco procurando aqui bem nesta linha. Isto é chamado um operador ternário. É uma declaração se mais condensada em uma linha. A condição é essa parte entre parênteses. É equivalente a dizer se j altura <- i - 1. E, em seguida, o que o conteúdo do bloco que se seriam são o espaço e, em seguida, o conteúdo do que a outra coisa seria se esse #. É, essencialmente, a atribuição de um espaço para essa variável. É colocar um espaço no conteúdo do bloco variável, Se esta condição for atendida, e se a condição não for atendida, então a variável bloco recebe este #. E depois, é claro, em vez de construir uma cadeia inteira e impressão de tudo no final essa solução imprime-o um personagem de cada vez. Muito legal. Outro par de coisas para olhar. Nós vamos passar para gananciosos. Agora, se olharmos para gananciosos, solução esta primeira usa esses # define um pouco. Temos uma constante definida para cada um dos diferentes números neste programa. Temos uma de centavos por dólar, uma para quartos, moedas, moedas e centavos, e agora, se desloque para baixo e ler o código, podemos ver um padrão-enquanto tudo impressão loop out. Tipo do cerne do problema foi perceber que você necessário para converter a bóia que você lê na do usuário para um número inteiro com precisão fazer a matemática, e isso é porque com números de ponto flutuante, como falamos na aula brevemente, não é possível representar com precisão cada valor único na linha de número porque há valores infinitos entre 3 e, digamos, 3,1 mesmo. Você pode ter 3,01 e 3,001 e 3,0001, e você pode continuar. Acontece sempre que você está trabalhando com o dinheiro, muitas vezes você quer convertê-lo em formato inteiro, de modo que você não está perdendo alguns centavos e esse tipo de coisa. Fazer isso e arredondamento foi fundamental. Esta solução utilizada perfeitamente simples algoritmo, grande, que diminua o número de centavos restantes, primeiro por trimestres, em seguida, por moedas, em seguida, por níqueis, em seguida, por tostões, e aumentando o número de moedas de cada vez. Outra solução que nós vamos ver, como eu diminuir o zoom e vá para a Revisão 4, teve um início muito semelhante, mas em vez utilizado div e mod bem aqui para calcular o número de centavos. Isso, o número de alojamentos é igual ao número de centavos divididos por 25, ea razão que isto funciona é porque estamos fazendo uma divisão inteira, por isso é descartar qualquer restante. [Estudante] Nós temos que comentar a pesquisa? Ela realmente depende. [Estudante] Você está comentando mais do que o código aqui. Sim, e por isso há um monte de diferentes filosofias sobre isso. Minha filosofia pessoal é que seu código é realmente a verdade, como seu código é o que está realmente em execução no computador, e para que o seu código deve ser legível possível para não necessitar de muitos comentários. Dito isso, quando você está fazendo coisas que são meio complicado matematicamente ou através de algoritmos, é bom para comentar os para que você possa adicionar uma dimensão extra, uma camada extra para quem está lendo o seu código. Nessas soluções, muitas vezes eles são comentados mais fortemente apenas porque nós queremos ser capazes de distribuí-los e ter pessoas buscá-las e lê-los muito facilmente. Mas, definitivamente, eu concordaria que este é pesado. [Estudante] Mas, quando em dúvida, vá mais pesado? Quando em dúvida, vá mais pesado. Algumas pessoas às vezes dizem 0 retorno ou algo assim. Eu acho que é um comentário ridículo. Claramente que é o que está acontecendo. Eu não preciso de Inglês para me dizer isso. Às vezes as pessoas escrevem coisas como "kthxbai!" Esse é um tipo de bonito, mas também não- que não está fazendo a diferença entre os pontos comentando ou não. Esses tipos de comentários são apenas ha, ha. Cool. Neste ponto, vamos começar a trabalhar no Conjunto de Problemas 3 seção de perguntas. Se vocês puxar isso de novo, como na semana passada, não estamos indo para assistir os curtas nesta seção. Nós vamos deixar vocês fazer isso em seu próprio tempo e falar sobre as perguntas. Mas agora nesta seção vamos gastar um pouco mais falando menos o básico de codificação como fizemos na semana passada, e em vez disso, vamos focar mais em um pouco mais da teoria, portanto, falar sobre a busca binária e de classificação. Desde aqueles de vocês que têm vindo a seguir, juntamente com a palestra, alguém pode me dar um resumo do que a diferença é entre busca binária e de busca linear? O que está acontecendo? Claro. Lineares pesquisas através de cada elemento na lista ordenada um por um por um por um por um, e busca binária divide a lista em dois grupos, Verifica se o valor teclas que você está procurando é maior ou menor que o valor do ponto médio que você acabou de encontrar, e se for menor, ele vai com a lista inferior e depois divide de novo, faz a mesma função todo o caminho até encontrar o ponto médio para ser igual ao valor propriamente dito. Direito. Por que nos importamos? Por que falamos de busca binária contra pesquisa linear? Sim. Binário é muito mais rápido, então se você dobrar o tamanho do problema ele dá mais um passo em vez de o dobro. Exatamente. Isso é uma grande resposta. Pesquisa linear é muito verificando um elemento de cada vez, e, como vimos no primeiro dia de aula Davi passou por seu exemplo livro de telefone e arrancou uma página do livro de telefone de cada vez e continuei a fazer isso mais e mais e outra vez, que vai levá-lo muito tempo para encontrar alguém no livro de telefone, a menos, claro, que ele estava procurando alguém no começo do alfabeto. Com busca binária, você pode ir muito mais rápido, e não é apenas duas vezes mais rápido ou 3 vezes mais rápido ou 4 vezes mais rápido. Mas o problema torna-se menor e menor e menor muito mais rápido. Para ilustrar isso, vamos começar a falar sobre o que está acontecendo quando escrevemos busca binária. O problema em questão é que se eu tiver uma matriz de números, por exemplo, 1, 2, 3, 5, 7, 23, 45, 78, 12,323, e 9 com uma tonelada de 0s depois, nós queremos ser capazes de descobrir muito rapidamente o que está em esse conjunto de números. Eu sei que isso parece um pouco bobo e um pouco artificial, porque agora ele é. Nós temos uma matriz que não tem elementos muito diversos em que, e se eu pedir um de vocês para descobrir se ou não 23 é na matriz, você pode fazer isso muito rapidamente apenas olhando para isso e me dizer sim ou não. O análogo a considerar é imaginar se isso fosse, digamos, uma planilha Excel com 10.000 linhas, 20.000 linhas. Claro, você pode fazer o comando F ou o F e controle de procurar alguma coisa. Você também pode usar os filtros e as coisas de busca, mas se você tinha que olhar através desse arquivo linha por linha por linha, que levaria muito tempo para encontrá-lo. É tipo como no exemplo do livro de telefone, também, onde ninguém olha através de uma página de um livro de telefone de cada vez. Normalmente, eles não abri-lo ao meio, ou, no caso de uma série de livros de telefone e dicionários onde você realmente tê-lo introduzido na primeira letra, você virar a primeira carta, abrir e começar a passar por lá. Me lembrar do seu nome novamente. >> Sam. Sam. Como disse Sam, que o processo de busca linear vai ser muito lento, e, em vez de busca binária, a forma como isto funciona é que cada vez que passar por uma iteração do nosso algoritmo de busca, vamos dividir a lista ao meio, essencialmente, em duas listas menores. E, em seguida, a próxima iteração do loop, vamos dividi-lo novamente em outras listas menores. Como você pode ver, o problema continua ficando menor e menor porque guardamos descartando metade da lista de cada vez. Como funciona esse descarte? Apenas como lembrete, o que vamos fazer, se fosse um computador e nós foram, digamos, procurando o número 5 na lista é que se escolher um número no meio. No meio da lista, porque não são 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 números, nós escolher o número, quer na posição de quarto ou na posição 5, e diria que o meio de nossa lista. Escolha número no meio. Então, assim como Sam disse, vamos testar para ver se esse número é igual para o número que queremos chegar ou o nosso número desejado. Se for igual, então nós encontramos isso. Nós ganhamos. Se não é igual, então há um par de casos. Os dois casos são ou o número tem de ser maior do que o número que estamos olhando, ou é menor que. Se for maior, vamos passar para a direita. E se é menos, nós nos movemos para a esquerda. E, então, repetir todo o processo novamente em cada metade da direita ou da metade esquerda da lista. O primeiro problema na seção de hoje é descobrir como podemos realmente começar a expressar isso no código C. Nós temos o pseudocódigo aqui. O que nós vamos começar a fazer é que eu vou puxar-se um novo espaço, salvar esta revisão para que tenhamos essas notas para mais tarde, vamos apagar tudo isso, e em seguida, copiar e colar a partir do conjunto de problemas esta informação em nossos espaços, e espero que isso não quebra. Perfeito. Se vocês todos fazem isso, copie e cole este código em seu novo espaço, em um em branco. Vamos tentar Daniel. Se você compilar e executar este programa, é que funciona? >> Não. O que está dizendo? Ele diz que o controle atinge final de não-void função. Sim, então deixe-me tentar executá-lo. Vocês já viram isso antes? Você sabe o que isso significa? Ok, vamos dissecar isso um pouco. Ele está dizendo, file.c na linha 9, coluna 1, temos um erro, como você disse, e ele diz que ele é decorrente do aviso de erro eo aviso tipo de retorno. Parece que alguma coisa está acontecendo com o tipo de retorno, o que faz sentido. Nós temos uma função não-nula, o que significa que temos uma função que não volta vazia. Uma função de vazio é um que se parece com esta: void foo (), e é nula, porque o tipo de retorno é nulo, o que significa que se nós tivéssemos alguma coisa aqui como um retorno, teríamos um erro do compilador para isso. No entanto, temos uma função não-nula. Nossa função não-nula neste caso é a nossa função de pesquisa porque tem um tipo de retorno de bool. Quando é dizendo que o controlo atinge o fim de uma função não nula, é porque a pesquisa não tem uma instrução de retorno. Ele não está retornando nada do tipo bool. Nós podemos consertar isso, eo que é que vocês pensam pesquisa deverá retornar por padrão? Qual deve ser o valor de retorno padrão de busca? Porque é o que podemos colocar no final. Charlotte, você tem alguma-? Verdadeiro ou falso? >> Verdadeiro ou falso. Qual? Falso. Eu não sei. Falso? Vamos tentar. Por que você diz return false? Isso é grande intuição. [Charlotte] Eu não sei. Nós vamos retornar false neste caso, porque este será o nosso padrão se por algum motivo a lista está vazia ou a agulha que está procurando não existe. Então, no final, se não retornar verdadeiro anteriormente nesta função, nós sempre sabemos que esta função vai dizer Não, não é na matriz. Não é no palheiro. Agora, se compilar e executar, deixe-me guardar este para que possamos puxar para cima. Agora, se compilar e executar o nosso programa, que constrói. Nós temos nosso prompt pouco. Se eu acertar 4-uh-oh. Ele não imprimir nada. Parece que tudo terminou bem. Nós temos que preencher este polegadas Nós conversamos sobre o algoritmo em pseudocódigo um pouco atrás. Deixe-me ver, senão este, e eu vou puxar o algoritmo de volta novamente. Vamos bater esse cara. Nope. Não é. Como podemos fazer isso? O que seria uma boa estratégia para o arranque esse código? Você tem que escolher um número no meio. Como é que vamos escolher um número no meio de uma matriz? Alguma sugestão? [Estudante] strlen dividido por 2. Strlen dividido por 2. Isso é um grande. Strlen trabalha com tipos especiais de matrizes. Que tipos de matrizes? Matrizes String, arrays de caracteres. É que mesmo tipo de conceito que queremos aplicar, mas não podemos usar strlen porque não temos uma matriz de caracteres. Nós temos uma matriz de inteiros. Mas o que strlen começar por nós? Você sabe o que fica para nós? [Estudante] strlen fica-nos o comprimento. Exatamente, fica-nos o comprimento. Strlen recebe o comprimento da matriz para nós. Como é que vamos conseguir isso em nosso programa de busca binária? Como você obter o comprimento de uma matriz? [Estudante] strlen? Você pode obter o comprimento de uma matriz formatada corretamente seqüência C com strlen. O problema, porém, é que não temos uma matriz de cadeia. Se olharmos para trás, neste código, temos essa matriz inteiro. Como sabemos quanto tempo é? [Estudante] Existe um equivalente para um ponto final, como int l ou algo assim? Acontece que há, na verdade, não é, e isso de certa forma, isso é uma daquelas coisas que é bom saber sobre C, que não há nenhuma maneira de obter o comprimento de uma matriz se tudo o que eu te dar é a matriz. A razão trabalha com cordas, a razão strlen obras, é porque se uma string está formatado corretamente, ele terá que especial caracter \ 0 no final. Você também pode imaginar se você tem uma string formatada incorretamente e não há nenhum caracter \ 0 lá, então a coisa toda não funciona. [Estudante] Você pode adicionar o \ 0? Poderíamos neste caso. Poderíamos acrescentar algum tipo de \ 0 ou algum tipo de significar personagem e então usar isso. Mas isso não é muito de ir trabalhar porque o 0 \ é para um tipo char, e aqui temos ints. A outra coisa é que, se fosse para usar um valor especial como -1 a marcar o final de uma matriz então nunca poderia armazenar um -1 em nossas matrizes inteiros. Nós estaríamos presos. Acontece que a única maneira de obter o comprimento de uma matriz em C é, na verdade, lembre-se que quando você configurá-lo e passá-lo ao redor com a matriz de modo que sempre que eu tenho uma função que vai fazer algum trabalho em um array de inteiros ou flutua ou duplica ou o que você tem, Eu também preciso dar a função comprimento da matriz, e isso é exatamente o que temos feito aqui na função de pesquisa. Se você olhar, o que fizemos quando passamos em nossa matriz aqui, que também passam no comprimento, o tamanho. Acontece que nós chamamos esta variável aqui, este parâmetro ou argumento. Isso é chamado de lista de argumentos da função ou lista de parâmetros, e estes são também chamados de argumentos ou parâmetros. As pessoas usam termos diferentes em momentos diferentes. Eu às vezes trocar-los pessoalmente. O que acontece é que esta variável aqui é um nome semelhante a esta # define-se aqui. Mas eles não são a mesma coisa. A capitalização não importa. Se você olhar para o que acontece aqui, nós declaramos nossa matriz int, o que nós chamamos de números. Nós demos o nosso tamanho, o que corresponde ao nosso # define-se no topo. Vai ser 8. E então, quando nós então chamar nossa função de pesquisa, logo abaixo, passamos o número que deseja pesquisar, o que temos solicitado, obtido a partir do usuário. Passamos na matriz, este números, e, depois, também têm de passar no tamanho da matriz, e, em seguida, o valor de tamanho 8 fica armazenado ou passados ​​para essa variável tamanho inteiro chamado. Temos o tamanho da matriz. Agora, se voltar para o que estávamos falando antes, Eu acho que Missy trouxe o ponto de que o que precisávamos fazer é obter o comprimento da matriz e dividir por dois, e que vai nos dar o ponto médio. Vamos ver. Posso ter alguém escrever esse e salvá-lo em seu espaço? Como cerca de Leila? Posso ter você escrever isso em? Escrever a primeira linha onde você toma o comprimento da matriz e obter o ponto médio e armazená-lo em uma nova variável. Vou te dar alguns segundos. Você está pronto? [Estudante inaudível] Claro, eu poderia ter você a calcular o ponto médio da matriz palheiro dentro da função de pesquisa utilizando o comprimento da matriz palheiro, que é a variável de tamanho? Nada complicado aqui. [Leila] tamanho Just / 2 e just- E salvá-lo, e aperte o botão Salvar-se aqui em cima, e vamos arrancá-la. Perfeito. Lá vamos nós. Impressionante. Como é, este vai compilar? [Leila] Não, ele precisa ser maior. [Nate] Sim, então o que precisamos fazer? [Leila] Como ponto médio int ou algo assim. Impressionante. Sim, vamos fazer isso, int size = ponto médio. Será que isto vai compilar? Vamos apagar este comentário e tirá-lo do caminho. O que não será compilado sobre isso? Nós não estamos fazendo nada com inteiro, por isso precisamos de imprimi-lo ou algo assim. Sim, exatamente. Nós vamos ter uma variável não utilizada. O que mais não vai trabalhar sobre isso? Eu acho que você disse alguma coisa, Sam. Ponto e vírgula. Sim, eu estou perdendo os pontos e vírgulas. Vai ser uma constante ao longo de todo o período. A última coisa que vou fazer é que eu vou colocar algum espaço em branco em ambos os lados deste operador aqui, já que é normalmente como fazemos de acordo com o nosso guia de estilo. Nós temos o ponto médio da nossa matriz. Agora, se nos lembrarmos de volta ao nosso algoritmo, qual foi o segundo passo que nós tivemos que fazer uma vez que temos o ponto médio? [Estudante] Se for maior [inaudível]. Sim, por isso temos de fazer algum tipo de comparação, eo que estamos comparando aqui? Você disse que se ele é maior que. O que há em que a sentença se refere? O número que aparece, se é maior do que o ponto médio, então vá até a matriz? Exatamente, por isso o número que aparece quando nós- A agulha, por isso estamos comparando com a agulha, eo que estamos comparando contra a agulha? Porque a agulha é o que estamos procurando. Estamos comparando-o a chegar ao ponto médio. Mas será que faz sentido para verificar se ponto médio = agulha? Isso faz sentido? Alguém discorda? Vamos tentar, se (ponto médio agulha ==). [Estudante] Não printf você o encontrou. [Nate] printf ("Nós descobrimos que \ n"); Caso contrário! Vou começar a fazer algo diferente aqui. Eu vou começar a colocar cintas em torno de se as declarações o tempo todo apenas porque se nós adicionamos mais coisas, então nós não temos os compiladores. Sim, Sam. Você tem um ponto. O problema é que o ponto central representa uma posição na matriz, mas você pode obtê-lo para representar o valor em que a posição da matriz. Isso é um grande ponto. Será que toda a gente ouvir o que Sam disse? Ele disse que como é ponto médio representa apenas uma posição na matriz, mas não é o elemento real na matriz. Se você pensar sobre o código como escrito agora, se olharmos para esta matriz aqui em baixo, que tem 8 elementos em que, o que é o valor do ponto médio vai ser nesta função? [Estudante] 4. [Nate] 4. Se olharmos para o número 4 - e nós podemos apenas executar esse código e colocar um rosto pouco triste aqui porque não achou-se executar esse código como é agora, carregando-o, construção, deixe-me rolar para baixo, e se olharmos para o número 4, que encontramos, mas não chegar a este printf sim. Uma razão é que nós não retornar true, mas nós realmente encontrar o número 4? E Sam é dizer não. O que nós encontramos? Nós realmente encontramos o ponto médio, que se olharmos para a matriz para cá, ele vai ser o elemento no índice 4 que estamos olhando, que é 23. Como é que vamos realmente ter esse elemento no ponto médio e não apenas o ponto médio em si? [Estudante] Nós entraria char ou algo assim? O que teria que fazer, só por curiosidade? Você pode elaborar um pouco mais? Tens de transformar a posição para o número, assim que você tem que fazer alguma ligação, eu acho que é char, mas pode não ser. Sim, isso é um bom ponto. Estamos fazendo um monte de posições esta convertendo em caracteres, esses personagens, durante os dois primeiros conjuntos de problemas. Acontece que aqui, isso é quase semelhante ao acessando o caráter om dentro de uma cadeia, se isso faz sentido. Aqui queremos acessar o elemento ponto médio. Como podemos fazer isso? Kevin, você tem alguma sugestão de como podemos fazer isso? Você poderia fazer palheiro, suporte aberto, médio, fechou suporte. Você pode escrever isso por nós? Salvá-lo aqui, e nós vamos puxar isso. Nós estamos olhando para essa linha 9, e nós estamos percebendo que nós não queremos comparar a agulha para o ponto médio, mas em vez disso, queremos comparar a agulha para o elemento no ponto médio posição dentro de nossa matriz palheiro. Cool. Lá vamos nós. Sim, isso parece muito bom, se (== agulha palheiro [ponto médio]). Nós encontramos. Agora, se executar o código de volta we'll-se um pouco-bit ele compila, ele é executado, e agora se olharmos para 4, não encontramos, porque agora estamos realmente começando a número 23. Nós estamos recebendo o valor de 23, e é isso que estamos comparando a nossa agulha. Mas isso é bom. Esse é um passo na direção certa. Isso é o que estamos tentando fazer. Nós não estamos tentando comparar a agulha contra posições na matriz mas sim contra os elementos reais da matriz. Se olharmos para trás novamente, agora na próxima etapa em nosso algoritmo, qual é o próximo passo? Leila já mencionado brevemente. [Estudante] Verifique se é maior ou menor do que e, em seguida, decidir qual o caminho a se mover. [Nate] Sim, então como é que vamos fazer isso? Você pode colocar em algum eu vou-salvar esta revisão, e, em seguida, se você colocar em algumas linhas que vai fazer isso. Sim, Charlotte. >> Eu tenho uma pergunta. Caso não seja ponto médio - 1, porque a primeira coisa é é 0 indexados, por isso, se nós colocamos 4, que não é realmente o personagem que está procurando? Sim, e o outro problema com que se- isso é uma grande captura, porque o que vai acabar acontecendo, possivelmente, se manter em movimento e nós nunca ajustar inicialmente? Eu acho que o que pode acabar fazendo é tentando acessar o elemento na posição 8 da matriz, que neste caso não existe. Vamos querer fazer algum tipo de contabilidade para o fato de que temos uma indexação zero. [Charlotte] Desculpe, eu quis dizer ponto médio - 1 entre colchetes. Nós podemos fazer isso. Voltaremos a esta questão em um pouco. Uma vez que começam a chegar ao looping real, que é quando nós vamos realmente ver isso entrar em jogo. Por enquanto, não podemos fazer isso, mas você está totalmente certo. Que a indexação zero terá um efeito que é preciso explicar. Vamos ver. Como é a maior e menor do que-? [Estudante] eu chegar a fazer o maior e menor do que a parte. Eu só não tinha certeza do que imprimir, se você achar que é menos do que o ponto médio palheiro ou superior. Aqui eu posso salvar o que I've- [Nate] Sim, se você salvar o que você tem, e nós vamos puxá-lo para cima. Lá vamos nós. [Estudante] E eu colocar pontos de interrogação para o que eu não sabia. [Nate] que parece ótimo. Aqui nós temos pontos de interrogação, porque ainda não sei o que nós vamos fazer muito ainda. O que nós queremos fazer-oops, temos algumas chaves tudo funky em nós. Vamos corrigir essas chaves. Lá vamos nós. E então o que nós queremos fazer, de acordo com o nosso algoritmo, se não encontrar a agulha? Dizer no caso em que a agulha é menor do que o que estamos olhando. Kevin. Só olhar para a meia esquerda. Certo, então vamos colocar um comentário aqui que diz "olhe para meia esquerda." E se a agulha é maior do que o palheiro no ponto médio, o que nós queremos fazer? [Estudante] Então você olha para o lado direito. Olhe para o lado direito, "olhar para a metade direita." Nada mal. Ok, então, neste momento, as coisas estão muito bem. O problema com o código como está escrito é o que? [Estudante] Você não tem parâmetros para as metades. Certo, que não têm pontos de extremidade para as duas metades. Também está indo só para passar por isso uma vez. Só vamos olhar para um ponto médio. Ou o elemento está lá, ou não é. A fim de completar isso, vamos precisar fazer algum tipo de repetição. Precisamos manter repetindo até descobrimos que ou o elemento está lá porque nós reduzimos e, finalmente, encontrou, ou não está lá porque nós olhamos através de todas as coisas nas metades apropriadas da matriz e descobriu que nada está lá. Sempre que tenho essa repetição acontecendo, o que é que vamos usar? [Estudante] Um loop. Algum tipo de laço. Sim. [Estudante] Podemos fazer um loop do-while e tê-lo fazer isso e, enquanto a agulha não não é igual-Estou certo de onde eu estava indo com isso. Mas tipo como fazer isso, desde que não valoriza o igual que a entrada do usuário. Sim, então vamos ver, como isso pode escrever-se? Você disse que vamos usar um laço do-while. Onde é que o fazer de início? [Estudante] Logo após o tamanho / 2. [Nate] Ok, eo que é que vamos fazer? Vamos preencher o tempo depois. O que vamos fazer? [Estudante] Não queremos fazer tudo o que temos na parte de se? [Nate] fazer tudo isso, ótimo. Copiar e colar. Oh, cara. Vamos ver se isso funciona, se pudermos guia sobre isso. Bonito. Ok, e salvar este para que vocês têm. Tudo bem, e nós vamos fazer isso enquanto- Qual era a condição, enquanto você estava depois? [Estudante] Enquanto a agulha não é igual, então como o ponto de exclamação. Mas eu não sei exatamente o que é ainda. [Nate] Sim, esta é uma maneira de fazê-lo. Sam, você tem um comentário? [Sam] me lembrei quando eu olhei para os vídeos, Eu tomei uma imagem de um dos o-como quando fizemos o pseudocódigo para ele, havia alguma relação entre max e min. Acho que foi algo como se o máximo é sempre menos de min. Entendi. [Sam] Ou como se Max não é inferior a min ou algo assim, porque isso significa que você pesquisou tudo. Sim, então o que é que soa como máximo e mínimo estavam se referindo? [Sam] valores que inteiros que vão mudar em relação a onde vamos colocar o ponto médio. Exatamente. [Sam] Nesse ponto, ele vai [inaudível] calcular o máximo e mínimo. Ponto médio é esta idéia de Max e min. Isso faz sentido para as pessoas? Se tivéssemos que começar a olhar para como nós vamos fazer essa iteração, você está totalmente certo que queremos usar algum tipo de do-while. Mas eu acho que, se lembrarmos o que está acontecendo no local dessa matriz eo que está realmente acontecendo! Vou escrever aqui- na primeira iteração de pesquisa binária, temos- Eu vou usar b e e para denotar o início. E então, o fim da nossa matriz. Sabemos que o começo é a 4 bem aqui, e nós sabemos que o fim está em 108. Dizer que estamos procurando o número 15. A primeira vez que fazemos isso, como vimos anteriormente, o ponto médio é ou vai ser 16 ou 23 dependendo de como calcular as coisas. Desde uniformemente dividindo no meio nos daria este espaço entre 16 e 23, não é possível dividi-lo uniformemente ou dividi-lo e chegar a um ponto médio verdadeiro. Nós vamos olhar para 16. Nós vamos realizar "Ei, 16> 15, que estamos procurando." Para, em seguida, olhar para a metade esquerda da matriz o que vai acabar fazendo está descartando esta porção superior inteira e dizendo: "Ok, agora o nosso ponto final vai ser aqui." A próxima iteração do nosso circuito, agora estamos olhando para essa matriz, ter eliminado eficazmente esta porção, porque agora se estiver a tomar o ponto médio como sendo a diferença entre o início e o fim, encontramos nosso ponto médio para ser de 8, que pode então testar 8 para ver onde é em relação ao número que estamos procurando, 15, acho que 15 é maior, por isso temos de passar para a parte direita da lista, que sabemos porque somos seres humanos, e podemos ver isso. Sabemos que a parte direita vai ser onde encontrá-lo, mas o computador não sabe que, assim que nós vamos fazer é que vai realmente ter este ir para cima, e agora o começo eo fim são o mesmo ponto, de modo que o ponto central torna-se o único número da lista, nesse ponto, que é de 15, e encontrou-o. Será que lançar alguma luz sobre onde este máximo toda e notação min vai, manter o controle dos pontos finais da matriz, a fim de descobrir como estreitar as coisas? O que aconteceria se não fosse igual a 15 agora? O que se estivéssemos olhando para 15 e, em vez disso, este número também foram 16? Nós diríamos, "Oh, é maior. Queremos voltar para a esquerda. " E nós mover a nossa e para a direita, em que ponto temos um terminal que seria conflitante. Não seria capaz de procurar qualquer mais elementos porque agora temos o nosso ponto final e nosso ponto de partida, o nosso máximo eo nosso min, estão agora viradas. Buscamos através de toda a matriz. Não consigo encontrar nada. Esse é o ponto em que nós queremos dizer: "Ok, vamos parar este algoritmo. Não encontramos nada. Nós sabemos que não está aqui. " Como é que isso vai? [Estudante] Como exatamente o computador mudar o final? Como o final acabar antes do início? O final acaba antes do início por causa da matemática que vamos fazer a cada vez que fazemos isso. A nossa forma de trocar é que se você olhar para a primeira vez que fazemos este swap em que tem início a 4 e a extremidade todo o caminho até a 108 e nosso ponto médio, digamos, em 16 - Eu estou indo para repor isso de volta para 15 se nós estamos olhando para o 15, sabíamos que o que fizemos quando fez a 16 e viu que era maior e queria descartar toda a parte direita da lista, vimos que o que nós queríamos fazer é mover este e aqui. Efetivamente, o e foi movido para um antes do ponto médio. Da mesma forma, quando fizemos esta iteração do algoritmo e o ponto médio era de 8, verificou-se que 8 <15, então nós queríamos para mover o b um passado do ponto médio. Agora, no início e no fim são os dois juntos no 15. Se tivéssemos sido acontecendo para procurar algum outro valor, e não 15, ou se este 15 tinha sido uma vez 16, teríamos encontrado que o e queremos passar uma antes do ponto médio. Agora o e estaria lá capotou menos do que o b. Vamos examinar como podemos realmente acabar este algoritmo de codificação. Nós sabemos que nós queremos ter esse cálculo ponto médio. Sabemos também que pretende controlar o início e o fim da matriz de nossa matriz atual, para que possamos descobrir onde esta metade esquerda da lista é e onde a metade direita da lista é. Nós fazemos isso com um início e fim, ou podemos chamá-los de mínimo e máximo. Vou usar começar e terminar este tempo. Quando começamos, se olharmos para o nosso exemplo aqui, nosso começo foi definida para o início da matriz, como natural. O índice foi isso? O que deve ser a nossa começar? Daniel. [Daniel] Haystack [0]. [Nate] Sim, então nós poderíamos defini-lo igual ao palheiro [0]. O problema, no entanto, é que esta não nos dá a posição do primeiro elemento. Isso dá-nos o índice do primeiro elemento ou o valor real em que a primeira posição. [Estudante] Isso irá converter para 0,20? [Nate] O que isto vai fazer é, bem, ele não vai fazer qualquer conversão. O que ele vai fazer é que vai armazenar um 4 em começar, e depois será difícil fazer comparações contra começar porque begin vai realizar o valor de 4, que é o início de nossa matriz, mas queremos acompanhar os índices na matriz ao contrário dos valores. Nós vamos realmente usar a 0, assim. Para o final da matriz-Charlotte trouxe esta um pouco mais cedo. Este é o lugar onde nós vamos levar em conta a indexação zero. Charlotte, que é o final da matriz? O que é o índice da extremidade? [Charlotte] Tamanho - 1. Sim, e qual o tamanho que devemos usar? Devemos usar o tamanho de capital ou tamanho minúsculo? Tamanho Capital. Neste caso, poderíamos usar o tamanho de capital. Se quiséssemos esta função para ser portátil e use esta função em outros programas, nós podemos realmente usar o tamanho minúsculo. É bom também. Mas Charlotte é totalmente certo que queremos ter tamanho - 1. Neste ponto [Estudante] Como é que você pode usar o tamanho maiúscula? Como é que nós poderíamos usar tamanho maiúscula? Acontece que estes # define são realmente, sob o capô, um texto como localizar e substituir, se isso faz sentido. Quando você compilar o código, a fase de pré-processamento do compilador passa o arquivo, e olha para todos os lugares que você escreveu tamanho capital, e substitui o texto, literalmente, com um 8, apenas como aquele. Nesse sentido, isso é muito diferente de uma variável. Ele não ocupa espaço na memória. É um truque simples substituição de texto. Neste caso, vamos usar o tamanho. A partir daqui, quero fazer algum tipo de repetição, e que estamos no caminho certo com nosso laço do-while. Queremos fazer algo até que uma condição não mais se, e como vimos anteriormente, vimos que essa condição era de fato que nós não queremos o fim ser menor do que a começar. Esta é a nossa condição de parada. Se isso ocorrer, nós queremos parar e declarar como "Ei, mas não encontramos nada." Para expressar isso, nós queremos usar algum tipo de laço. Neste caso, seria um loop do-while, um loop, loop de um tempo? Nós temos um laço do-while aqui. Você caras como essa abordagem? Você acha que devemos tentar uma abordagem diferente? Kevin, todos os pensamentos? Nós poderíamos ter um loop while porque sabemos máximo seria maior do que a de qualquer maneira min iniciais. Sim, por isso não há inicialização que precisa acontecer. Aqueles laços fazer enquanto-são grandes quando você tem algo para inicializar antes depois testar, enquanto aqui sabemos que não vamos manter reinitializing tanto começar e terminar cada volta do loop. Nós sabemos que nós queremos para inicializá-los, em seguida, verificar a nossa condição. Neste caso, eu realmente ir com um loop while simples. Acontece que fazer enquanto loops são usados ​​bastante raro. Um monte de lugares nem mesmo ensinam que enquanto loops. Eles são bons para lidar com a entrada do usuário, de modo que temos visto muitos deles até agora. Mas normal para e enquanto laços são muito mais comuns. Acontece que essa condição como escrito não vai realmente fazer-nos muito bem, e por que isso? Sinto muito, eu não sei o seu nome. Estou Jerry. >> Desculpa? B é-O-R-L-I. Ah, ok. Eu não vejo você na minha lista. Ah, é porque, oh, isso faz sentido. Você tem uma idéia de por que isso loop while pode não funcionar como pretendido, como escrito com a condição? [Jerry] Quer dizer, como você quer todo o material depois de no-? Sim, então essa é uma. Talvez tenhamos de colocar todas essas coisas para o loop while, o que é totalmente verdade. A outra coisa que é um pouco mais problemático, porém, é que esta condição não funciona. [Estudante] Você precisa lançá-lo. Certo, então esta condição não será sempre verdade, inicialmente a maneira que nós conversamos sobre isso. Queremos fazer algo até > Além disso começar? [Estudante] No final. Porque é calculado apenas metade do comprimento. Você precisa adicionar a começar. [Nate] O que este cálculo para nós? Se pensarmos sobre o fim desta primeira iteração do loop, final vai ser no índice de posição 7. Comece está na posição 0. Lembre-se, nós estamos olhando para qualquer posição 3 ou da posição 4. Se olharmos para essa matemática, apenas para torná-lo um pouco mais tangível, colocar alguns números aqui, temos 7, 0, para 7-0, e depois / 2 é 3 na divisão inteira, o que é. Então precisamos então adicionar de volta o nosso começar? Nós não fazer neste caso. Na primeira iteração, ele vai ficar bem, porque começar é 0. Mas à medida que avançamos, nós realmente só precisa de todos final - comece / 2. Há um outro truque aqui, e que é um saber de precedência. [Estudante] Precisamos de parênteses? [Nate] Exatamente, e isso é porque se não colocar esses parênteses, a seguir esta linha será interpretado em vez como (final) - (início / 2), que definitivamente não quer. Cuidado com as regras de precedência. [Estudante] Por que não é acabar + começar? Por que não é acabar + começar? [Estudante] Por que não é isso? Por que seria +? Eu acho que você está certo. [Estudante] Porque é a média? [Nate] + End começar, você está totalmente certo. Uau, eu totalmente gozado. Você está certo. Se estivéssemos fazendo o menos, gostaríamos de acrescentar a começar para trás dentro Neste caso, você é muito certo que queremos tomar a média dos dois, assim que nós queremos para adicioná-los, ao invés de subtrair-los. [Estudante] Isso também funciona se você fez final - começar / 2 + começar. Seria se não fizermos-Acredito que sim. Por exemplo, se estivéssemos olhando para começar, e mudamos isso aqui ao 15. Agora é começar na posição 2. Final é na posição 7. Se subtrair-los, temos 5. Divida isso por dois, temos 2. E, então, adicionar 2 de volta, e que nos leva para a posição 4, que está aqui, que é o ponto médio. [Estudante] Precisamos cuidar de embrulho? Em que sentido é que precisamos cuidar de embrulho? Se a soma ou a diferença entre dependendo da forma como o fazemos não é um número par. Em seguida, o computador fica confuso se quando é 2,5; se você se mover para a esquerda ou para a direita para determinar qual é o ponto médio? Entendi. Acontece que com a divisão inteira, nós nunca obter esses números de ponto flutuante. Nós nunca obter o decimal. É totalmente descartada. Se você tem um computador dividir duas variáveis ​​int e uma é 7, e o outro é 2, você não vai ter como resultado 3,5. Ele vai ficar 3. O restante será descartado, por isso é efetivamente arredondamento Nem um, mas sim um chão, se vocês estão familiarizados com que, em matemática, onde descartar completamente a decimal, e por isso você está, essencialmente, truncando-lo para o mais próximo posições, para o número inteiro mais próximo. [Estudante] Mas então isso é problemático porque se você tem um conjunto de sete elementos em seguida, que assume automaticamente o elemento 3 para fora do ponto central, em vez do 4. Como lidar com isso? É problemático porque se tivéssemos uma matriz de 7, ele iria pegar o terceiro lugar do quarto. Poderia explicar um pouco mais? [Estudante] Porque se você tem 7 elementos, então o elemento 4 seria o ponto médio, certo? Lembre-se seu comentário sobre ser zero indexados, no entanto. [Estudante] Sim, então na posição 3. Esse seria o ponto médio. Sim. Ah, ok. Eu vejo o que você quer dizer. É meio estranho, como se acostumar com esta noção de livrar-se de casas decimais. Isso é um grande ponto. Vamos acabar com isso. Nós calculamos o ponto médio. Estamos testando para ver se a nossa agulha é igual ao valor médio. Estamos imprimindo que encontramos, mas realmente, o que nós queremos fazer nesta situação? Descobrimos que, por isso queremos que o chamador saiba que nós encontramos. Nós temos uma função que é uma função booleana digitado. A nossa forma de sinalizar para o chamador de nossa função de que estamos prontos para ir é que dizemos: "Ei, isso é verdade." Como poderíamos fazer isso, Kevin? Você está acenando com a cabeça. >> [Kevin] retorno Adicionar verdade. [Nate] Exatamente, retornar true. Agora, se não é igual, como é que olhamos para o lado esquerdo? Alguma idéia? Stella, alguma idéia? Você precisa definir uma nova posição para o final. Sim. Então, nós temos que fazer a posição de ponto médio - o fim. Grande. Precisamos definir uma nova posição para o final olhar para a metade esquerda. Isso foi o que falamos antes, onde Eu continuo voltando para este exemplo. Tenho a começar aqui, e então eu tenho o fim de tudo até aqui. Mais uma vez, se nós estamos olhando para 15, e nosso ponto médio é de 16 anos, e percebemos, "Oops, 16 é maior. Queremos passar para a meia esquerda. " Nós, então, passar o fim do 15, e fazemos isso tomando um longe do ponto médio e da definição que o nosso novo fim. Da mesma forma, se quisermos olhar para a metade direita, como é que vamos fazer isso? Você tem uma idéia? [Estudante] Você acabou de começar a definir ponto médio + 1. [Nate] Grande. E agora no caso que nós não encontrar nada, não que ficar resolvido por nós? Daniel, isso se levados em conta, de para nós? [Daniel] Não. [Nate] Se fizermos isso através da matriz inteira e não encontrar nada, onde teria que ser cuidado, ou devemos cuidar dela? [Daniel] A condição enquanto. [Nate] Sim, a condição de tempo, exatamente. Ele vai cuidar de passar por toda a matriz se não encontrar nada. Este loop while vai acabar. Nós nunca terá encontrado esta condição, e podemos retornar falso. Nós também pode deixar isso se aqui como esta porque se esta afirmação é verdadeira se, e nossa função vai voltar, e assim nós vamos essencialmente abortar esta função neste momento quando retornar true. Mas o que acontece com esta estrutura aqui? Será que isto vai funcionar totalmente, ou se há alguma falha lógica aí? Há alguma falha lógica lá, com a forma como ele é criado. O que pode ser? [Estudante] Por que você precisa - e + 1s? Que define a nossa matriz para ser nosso novo meia esquerda e meia direita. [Estudante] Mas por que você não poderia fazê-lo sem o - 1s e 1s +? [Nate] Nós podemos defini-lo igual ao ponto médio? O que pode ser problemático nisso? [Estudante] Eu acho que é ineficiente porque você está verificando um valor que já foi verificado. [Nate] Exatamente, por isso Sam é totalmente certo. Se você definir o fim eo início igual ao ponto médio em vez de - 1 e + 1 reflexivamente, em algum momento, no futuro, vai acabar verificar o ponto médio novamente. [Estudante] eu comecei a pset, e então eu tive algo parecido onde eu esqueci o 1 +, e ele ficou preso em um loop infinito. Certo, porque em algum momento você nunca vai se começar e terminar que realmente se sobrepõem. Cool. Há mais uma falha lógica, e isso é que este deve ser definitivamente uma pessoa se. Por que poderia ser? A razão é que não é uma pessoa se-você viu isso, Kevin? [Kevin] Sim, porque você está mudando o ponto final. [Nate] Exatamente. Estamos mudando o ponto final, e se for escrito assim we'll-criar espaços entre- ele irá verificar este caso. Neste caso, se for bem sucedido, irá abortar fora da função. Em seguida, ele irá verificar este caso seguinte, e se esta for bem sucedida, irá ajustar o ponto final, e depois continuará e verifique neste caso. Mas neste momento, não quer que ele continue a verificar. Felizmente, não temos redefinir o ponto central aqui, e sabemos que este caso não terá sucesso. Mas nós definitivamente queremos colocar o outro se lá apesar de que poderia em caso esta uma vez que não está ajustando o ponto médio, teria que fazer a diferença? Não, porque todos estes casos são exclusivas. Mais uma vez, foi mal. Não, eu acho, preciso disso mais se. Nós podemos dar-lhe uma tentativa e executá-lo e ver o que acontece. Edifício, um erro ocorreu. Provavelmente é porque eu deixei estes de b e e, em aqui. Eu tenho mais daqueles no topo? Ele não se parece com ele. Nós zoom out, construir, lá vai, agora se procurar 15, Sim. Deixe-me fazer zoom in 15, sim. Nós podemos executá-lo novamente. Upload de código-fonte, a construção, em execução. Podemos procurar por algo como 13, e nós não temos nada de imprimir, por isso não está descobrindo que para nós. Isso é ótimo, porque ele não está em nossa lista. Estamos agora fora do tempo. Isso vai ser ele para esta semana. Obrigado por se juntar, e vê-lo mais tarde. [CS50.TV]