>> [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]