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