>> 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 està sent implementat com una recerca lineal.
Però es pot fer molt millor que això.
Hi lineal s'implementa a O de n temps, el 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é, donem una ullada a 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 un llibre de telèfon a la meitat
pàgina en la Setmana 0.
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, des de 3, 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.
De manera que el seu extrem dret pot prémer la recerca surt una miqueta més,
i així successivament i així successivament, fins que a trobar el seu agulla.
>> Així que el que fa el pseudo- codi sembla?
Bé, ja que estem encara mirant a través de la llista i tot i així tenir
elements que ha de buscar, ens prenen el centre de la llista i comparar aquesta
valor mitjà de la 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 rebutjar el medi correcte 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 han trobat l'agulla, però, A continuació, tornarà fals.
A causa de que l'agulla sens dubte no està al paller.
>> Ara, una cosa polida sobre aquest pseudo codi binari de cerca és que pot
interpretar ja sigui 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 endavant en el curs.
Però no saben que és una opció si vol provar.