>> [REPRODUCCIÓ DE MÚSICA]
>> ZAMYLA CHAN: La primera cosa que vostè podria avís sobre troballa és que ja
haver codi escrit per a nosaltres.
Això es diu codi de distribució.
Així que no només estem escrivint la nostra pròpia codi des de zero ja.
Més aviat, estem omplint els buits en algun codi preexistent.
>> El programa find.c sol · licita números per omplir el paller, cerca la
Haystack per una agulla enviat pels usuaris, i ho fa cridant a classificar i
de recerca, funcions definides en helpers.c.
Així find.c està ja escrit.
El seu treball és escriure ajudants.
>> Llavors, què estem fent?
Estem implementant dues funcions.
Cerca, que retorna true si un valor es troba al paller, tornant
false si el valor és no en el paller.
I llavors nosaltres també estem implementant espècie que ordena la matriu anomenada valors.
>> Així que anem a abordar en aquesta categoria.
Cercar Actualment s'implementa com un recerca lineal, però es pot fer molt
millor que això.
Hi lineal s'implementa a O de temps n, que és bastant lent.
Encara que, pot buscar qualsevol llista que se li dóna.
El seu treball consisteix a posar en pràctica la recerca binària, que s'ha quedat temps O de registre núm.
Això és bastant ràpid.
>> Però hi ha una condició.
Cerca binària només pot buscar a través de les llistes de pre-ordenats.
Per què?
>> Bé anem a veure un exemple.
Donada una matriu de valors, el paller, estarem buscant
per una agulla.
I en aquest exemple, el nombre enter 3.
La forma en què la recerca binària funciona és que es compara el valor mitjà de
la matriu a l'agulla, igual que la manera obrim una agenda per al medi
pàgina en la setmana zero.
>> Així que després de comparar el valor mitjà de l'agulla, es pot descartar tampoc la
esquerra o la meitat dreta de la matriu estrenyent els seus límits.
En aquest cas, ja que tres, la nostra agulla, és menys de 10, el valor mitjà, la
dret d'Unió es reduirà.
Però tractar de fer que els seus límits el més ajustat possible.
Si el valor mitjà no és l'agulla, llavors vostè sap que vostè no ha de
incloure en la seva recerca.
Així que estàs en el cert límit pot prémer la recerca surt una miqueta més,
i així successivament i així successivament fins a trobar el seu agulla.
>> Llavors, què fa el pseudocodi sembla?
Bé, mentre que encara estem mirant a través de la llista i tot i així tenir elements per
Cerca a, prenem la meitat de la llista, i comparar aquest valor mitjà de
nostra agulla.
Si són iguals, llavors això vol dir que hem trobat l'agulla i podem
return true.
>> En cas contrari, si l'agulla és menys de el valor mitjà, llavors això vol dir que
pot descartar la meitat dreta, i just buscar el costat esquerre de la matriu.
En cas contrari, anem a buscar la costat dret de la matriu.
I al final, si vostè no té cap més elements que deixen de buscar, però que
no ha trobat el seu agulla encara, llavors vostè return false perquè l'agulla
definitivament no es troba en el paller.
>> Ara, una cosa polida sobre aquest pseudocodi en recerca binària és que pot ser
interpretar-se com un procés iteratiu o implementació recursiva.
Així que seria recursiu si es diu la funció de cerca a la recerca
funcionar en qualsevol de la meitat de la matriu.
Anem a cobrir la recursivitat una mica més tard en el per descomptat, però sí sabem que es tracta d'un
opció si voleu provar.
>> Ara donem una ullada a classe.
Ordenar pren una matriu i el nombre sencer n, que és la mida de la matriu.
Ara bé, hi ha diversos tipus diferents de les classes, i es pot veure en alguns
pantalons curts per a demostracions i explicacions.
El tipus de canvi de la nostra funció de classificació és nul · la.
Així que això significa que no anem per retornar qualsevol matriu d'ordenació.
Estem realment canviarà la mateixa matriu que es va passar a nosaltres.
>> I això és possible perquè les matrius són passen per referència a C. Ara anem a
veure més sobre això més endavant, però el diferència essencial entre passar
en una mena sencer i passa en una matriu, és que quan es
passar en un enter, C és només va a fer una còpia d'aquest sencer i passar
a la funció.
No es modificarà la variable original una vegada que la funció ha acabat.
Amb una matriu, d'altra banda, és no farà una còpia, i vostè
en realitat ser l'edició de la si molt array.
>> Així que un tipus d'espècie és el tipus de selecció.
L'ordenació per selecció Funciona a partir de les Al principi, i després iterar
una vegada i trobar l'element més petit.
I llavors canvies que els més petits element amb la primera.
I llavors vostè es mou al segon element , Cerca la següent més petita
element, i després d'intercanvi que amb la segon element de la matriu, ja
el primer element apareix ordenat.
I llavors vostè continua per a cada element en la identificació de la més petita
valor i la barata d'una ullada.
>> Per I és igual a 0, el primer element a n menys 1, vas a comparar
cada valor següent després d'això i trobar l'índex del valor mínim.
Quan trobi l'índex de valor mínim, vostè pot canviar el valor de la matriu
mínim i varietat I.
>> Un altre tipus d'espècie que pugui implementar és l'ordenació de bombolla.
Així es repeteix bombolla ordenar més de la llista la comparació dels elements adjacents i
l'intercanvi dels elements que estan en l'ordre equivocat.
I d'aquesta manera, l'element més gran burbujeará fins al final.
I la llista s'ordena una vegada més elements s'han intercanviat.
>> Així que aquests són dos exemples d'una espècie algoritmes que es poden implementar per
el programa de recerca.
Quan acabi d'ordenar i tens Cerca fet, hagi acabat.
El meu nom és Zamyla, i això és CS50.
>> [REPRODUCCIÓ DE MÚSICA]