[Música tocando] ZAMYLA CHAN: A primeira coisa que você pode aviso sobre descoberta é que já ter o código escrito para nós. Isto é chamado código de distribuição. Portanto, não estamos apenas escrevendo o nosso próprio código do zero mais. Em vez disso, estamos preenchendo os vazios em algum código pré-existente. O programa find.c solicita números para preencher o palheiro, busca o monte de feno para uma agulha usuário enviou, e ele faz isso chamando classificar e busca, funções definidas em helpers.c. Assim find.c é escrita já. O seu trabalho é escrever ajudantes. Então, o que estamos fazendo? Estamos implementando duas funções. Pesquisa, que retorna true se um valor é encontrado em palheiro, retornando false se o valor é não no palheiro. E então nós também estamos implementando tipo que classifica o array chamado valores. Então, vamos enfrentar pesquisa. Pesquisa é implementado atualmente como um busca linear, mas você pode fazer muito melhor que isso. Busca linear é implementada em O de tempo n, o que é bastante lento. Embora, ele pode pesquisar qualquer lista que lhe é dado. Seu trabalho é a implementação de busca binária, que tem tempo de execução O de log n. Isso é muito rápido. Mas há uma condição. Pesquisa binária só pode procurar através de listas pré-ordenadas. Por que isso? Bem, vamos olhar um exemplo. Dada uma matriz de valores, o palheiro, vamos estar a olhar para uma agulha. E, neste exemplo, o número inteiro três. A maneira que busca binária funciona é que compararmos o valor médio de a matriz para a agulha, bem como a forma como abrimos uma agenda para o meio Página na semana zero. Então, depois de comparar o valor médio para a agulha, você pode descartar ou a esquerda ou da metade direita da matriz apertando os seus limites. Neste caso, uma vez que três, a agulha, é inferior a 10, o valor médio, o certo limite pode diminuir. Mas tente fazer seus limites tão apertada quanto possível. Se o valor do meio não é a agulha, então você sabe que você não precisa incluí-lo em sua busca. Então você está certo limite pode apertar a limites da pesquisa apenas um pouquinho mais, e assim por diante e assim por diante até você encontrar sua agulha. Então, o que o pseudocódigo parece? Bem, enquanto nós ainda estamos olhando através da lista e ainda tem elementos para olhar nos, tomamos a meio da lista, e comparar o valor médio para nossa agulha. Se eles são iguais, então isso significa que nós temos encontrou a agulha e podemos return true. Caso contrário, se a agulha for inferior a o valor médio, em seguida, isso significa que pode descartar a metade direita, e apenas pesquisar o lado esquerdo da matriz. Caso contrário, nós vamos procurar o lado direito da matriz. E, no final, se você não tem qualquer mais elementos da esquerda para a busca, mas você não encontrou sua agulha ainda, então você return false porque a agulha Definitivamente, não é no palheiro. Agora, uma coisa interessante sobre este pseudocódigo em busca binária é que ele pode ser interpretado como um iterativo ou implementação recursiva. Portanto, seria recursiva se chamado a função de pesquisa dentro da pesquisa funcionar em qualquer uma das metades da matriz. Nós vamos cobrir recursão um pouco mais tarde no claro, mas sei que ele é um opção se você gostaria de tentar. Agora vamos olhar para o tipo. Ordenar recebe um array eo inteiro n, que é o tamanho da matriz. Agora, existem vários tipos diferentes das sortes, e você pode olhar para alguns shorts para demonstrações e explicações. O tipo de retorno para o nosso função de classificação é nula. Então isso significa que nós não vamos para retornar qualquer matriz de tipo. Na verdade, estamos indo para mudar a própria matriz que foi passado para nós. E isso é possível porque as matrizes são passados ​​por referência em C. Agora vamos veja mais sobre isso mais tarde, mas o diferença essencial entre passagem em algo como um inteiro e passagem em uma matriz, é que quando você passar em um inteiro, C só vai fazer uma cópia desse inteiro e passar lo para a função. A variável original não será alterado uma vez que a função é terminada. Com uma disposição, por outro lado, é não vai fazer uma cópia, e você vai na verdade, ser de editar o si muito array. Assim, um tipo de espécie é o tipo de seleção. O tipo de seleção funciona a partir de o início, e então você iterar mais e encontrar o menor elemento. E então você trocar que a menor elemento com o primeiro. E então você se move para o segundo elemento , Encontrar o próximo menor elemento, e trocar isso com o segundo elemento na matriz, porque o primeiro elemento já está classificada. E então você continua para cada elemento de identificação do menor valor e troca-lo para fora. Pois é igual a 0, o primeiro elemento para n menos 1, você está indo para comparar cada valor seguinte e depois que encontrar o índice do valor mínimo. Depois de encontrar o índice de valor mínimo, você pode trocar o valor de um array I. mínimo e disposição Outro tipo de classificação que você pode implementar é bubble sort. Então repete Bubble Sort sobre a lista comparar os elementos adjacentes e trocando os elementos que estão na ordem errada. E deste modo, o maior elemento vai borbulhar até o fim. E a lista é ordenada uma vez mais elementos foram trocados. Então esses são dois exemplos de tipo algoritmos que você pode implementar para o programa de descoberta. Uma vez que você terminar de classificação, e você tem feito de busca, você está acabado. Meu nome é Zamyla, e este é CS50. [Música tocando]