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.