[Música tocando] ZAMYLA CHAN: A primeira cousa que pode aviso sobre descubrimento é que xa ter o código escrito para nós. Isto chámase código de distribución. Polo tanto, non estamos só escribindo o noso propio código de cero máis. Pola contra, estamos cubrindo os baleiros nalgún código pre-existente. O programa find.c solicita números para cubrir o palheiro, busca o chea de feno para unha agulla usuario enviou, e el fai iso chamando clasificar e busca, funcións definidas en helpers.c. Así find.c está escrita xa. O seu traballo é escribir axudantes. Entón, o que estamos facendo? Estamos aplicando dúas funcións. Investigación, que retorna true se un valor se atopa en palheiro, retornando false se o valor é non no palheiro. E entón nós tamén estamos aplicando tipo que clasifica o array chamado valores. Entón, imos afrontar investigación. Busca é aplicado actualmente como un busca lineal, pero pode facer moito mellor que iso. Busca linear é aplicada no de tempo n, o que é moi lento. Aínda que, pode buscar calquera lista que lle é dado. O seu traballo é a implementación de busca binaria, que ten tempo de execución O de rexistro n. Isto é moi rápido. Pero hai unha condición. Busca binaria só pode buscar mediante listas pre-ordenada. Por que isto? Ben, imos ollar un exemplo. Dada unha matriz de valores, o palheiro, imos estar a ollar para unha agulla. E, neste exemplo, o número enteiro tres. O xeito que busca binaria funciona é que compararmos o valor medio de a matriz para a agulla, así como o xeito no que abrimos unha axenda para o medio Páxina a semana cero. Entón, despois de comparar o valor medio para a agulla, pode descartar ou a esquerda ou da metade dereita da matriz axustado os seus límites. Neste caso, xa que tres, a agulla, é inferior a 10, o valor medio, o certo límite pode diminuír. Pero probe facer os seus límites tan axustado como sexa posible. O valor do medio non é a agulla, entón vostede sabe que non é preciso inclui-lo na súa procura. Entón está certo límite pode usar a límites da investigación só un pouquiño máis, e así por diante e así por diante ata atopa a súa agulla. Entón, o que o pseudocódigo parece? Así, mentres que nós aínda estamos mirando a través da lista e aínda ten elementos para ollar nos, tomamos a través da lista, e comparar o valor medio para nosa agulla. Se son iguais, entón iso significa que temos atopou a agulla e podemos return true. En caso contrario, se a agulla é inferior a o valor medio, a continuación, isto significa que pode descartar a metade dereita, e só buscar o lado esquerdo da matriz. En caso contrario, nós imos buscar o lado dereito da matriz. E, ao final, se non ten ningún máis elementos de esquerda a procura, pero non atopou a súa agulla aínda, entón return false porque a agulla En definitiva, non é no palheiro. Agora, unha cousa interesante sobre este pseudocódigo en busca binaria é que pode ser interpretado como un iterativo ou implantación recursiva. Polo tanto, sería recursiva se chama a función de investigación dentro da investigación funciona en calquera das metades da matriz. Nós imos cubrir recursão un pouco máis tarde no claro, pero sei que el é un opción se quere probar. Agora imos ollar para o tipo. Ordenar recibe un array eo enteiro n, que é o tamaño da matriz. Agora, hai varios tipos diferentes das sortes, e pode ollar para algúns shorts para demostracións e explicacións. O tipo de retorno para o noso función de clasificación é nula. Entón iso significa que nós non imos para voltar calquera matriz de tipo. En realidade, estamos indo a cambiar a propia matriz que foi pasado para nós. E isto é posible porque as matrices son pasados ​​por referencia en C. Agora imos ver máis sobre iso máis tarde, pero o diferenza esencial entre pasaxe en algo así como un enteiro e paso nunha matriz, é que cando pasar nun enteiro, C só vai facer unha copia deste enteiro e pasar lo para a función. A variable orixinal non será modificado xa que a función é rematada. Cunha disposición, por outra banda, é Non vai facer unha copia, e vai en realidade, ser de editar o si moi array. Así, un tipo de especie é o tipo de selección. O tipo de selección funciona desde o principio, e entón iterado máis e atopar o menor elemento. E entón intercambiar que a menor elemento co primeiro. E entón se move para o segundo elemento , O seguinte menor elemento, e cambiar iso co segundo elemento na matriz, xa o primeiro elemento xa está clasificada. E entón segue para cada elemento de identificación do menor valor e intercambio-lo para fóra. Pois é igual a 0, o primeiro elemento para n menos 1, está indo a comparar cada valor seguinte e logo que atopar o índice do valor mínimo. Despois de atopar o índice de valor mínimo, pode cambiar o valor dun array I. mínimo e disposición Outro tipo de clasificación que se pode aplicar é bubble sort. Entón repite Bubble Sort sobre a lista comparar os elementos adxacentes e cambiando os elementos que están na orde errada. E deste xeito, o maior elemento vai borbulhar ata o final. E a lista é ordenada unha vez máis elementos foron trocados. Entón eses son dous exemplos de tipo algoritmos que pode aplicar para o programa de descubrimento. Unha vez que termine de clasificación, e ten feito de procura, está acabado. O meu nome é Zamyla, e este é CS50. [Música tocando]