>> 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 especie, que clasifica o array chamado valores.
Entón, imos afrontar investigación.
>> Busca é aplicado actualmente como unha busca linear.
Pero pode facer moito mellor do que iso.
Busca linear é aplicada en O de n tempo, 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 dar un ollo a un exemplo.
Dada unha matriz de valores, o palheiro, imos estar a ollar
por unha agulla, e neste exemplo, o número enteiro 3.
>> O xeito que busca binaria funciona é que compararmos o valor medio de
a matriz para a agulla, así como o xeito no que abrimos un libro de teléfono para o medio
páxina na Semana 0.
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 3, 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.
Polo tanto, o seu límite dereito pode usar a límites da investigación só un pouquiño máis,
e así por diante e así por diante, ata que atopa a súa agulla.
>> Entón, o que fai o pseudo código se parece?
Así, mentres que nós aínda estamos mirando a través a lista e aínda ter
elementos para ollar, tomamos o medio da lista e comparar isto
valor medio para o noso 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 voltar false.
Porque a agulla definitivamente Non é en palheiro.
>> Agora, unha cousa interesante sobre este pseudo código en busca binaria é que pode
pode interpretar 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 algo máis tarde no curso.
Pero sei que é unha opción Se desexa probar.