ZAMYLA CHAN: La primera cosa que usted podría aviso sobre hallazgo es que ya haber código escrito para nosotros. Esto se llama código de distribución. Así que no sólo estamos escribiendo nuestra propia código desde cero ya. Más bien, estamos llenando los vacíos en algún código preexistente. 

El programa find.c solicita números para llenar el pajar, busca la Haystack por una aguja enviado por los usuarios, y lo hace llamando a clasificar y de búsqueda, funciones definidas en helpers.c. Así find.c está ya escrito. Su trabajo es escribir ayudantes. 

Entonces, ¿qué estamos haciendo? Estamos implementando dos funciones. Buscar, que devuelve true si un valor se encuentra en el pajar, volviendo false si el valor es no en el pajar. Y entonces nosotros también estamos implementando especie, que ordena la matriz llamada valores. Así que vamos a abordar en esta categoría. 

Buscar actualmente está siendo implementado como una búsqueda lineal. Pero se puede hacer mucho mejor que eso. La búsqueda lineal se implementa en O de n tiempo, lo que es bastante lento, aunque puede buscar cualquier lista que se le da. Su trabajo consiste en poner en práctica la búsqueda binaria, que se ha quedado tiempo O de registro n. Eso es bastante rápido. 

Pero hay una condición. Búsqueda binaria sólo puede buscar a través de las listas de pre-ordenados. ¿Por qué? Bueno, echemos un vistazo a un ejemplo. Dada una matriz de valores, el pajar, vamos a estar buscando para una aguja, y en este ejemplo, el número entero 3. 

La forma en que la búsqueda binaria funciona es que se compara el valor medio de la matriz a la aguja, al igual que la forma en abrimos un libro de teléfono a la mitad página en la Semana 0. Así que después de comparar el valor medio de la aguja, se puede descartar tampoco la izquierda o la mitad derecha de la matriz apretando sus límites. En este caso, desde 3, nuestra aguja, es menos de 10, el valor medio, la derecho de Unión se reducirá. 

Pero tratar de hacer que sus límites lo más ajustado posible. Si el valor medio no es la aguja, entonces usted sabe que usted no tiene que incluirlo en su búsqueda. De modo que su extremo derecho puede apretar la búsqueda sale un poquito más, y así sucesivamente y así sucesivamente, hasta que a encontrar su aguja. 

Así que lo que hace el pseudo- código parece? Bueno, ya que estamos todavía mirando a través de la lista y aún así tener elementos que debe buscar, nos toman el centro de la lista y comparar esa valor medio de nuestra aguja. Si son iguales, entonces eso significa que hemos encontrado la aguja, y podemos return true. 

De lo contrario, si la aguja es menos de el valor medio, entonces eso significa que puede desechar el medio correcto y justo buscar el lado izquierdo de la matriz. De lo contrario, vamos a buscar la lado derecho de la matriz. Y al final, si usted no tiene ninguna más elementos que dejan de buscar, pero que no han encontrado la aguja, sin embargo, A continuación, volverá falso. Debido a que la aguja sin duda no está en el pajar. 

Ahora, una cosa aseada sobre este pseudo código binario de búsqueda es que puede interpretarse ya sea como un proceso iterativo o implementación recursiva. Así que sería recursivo si se llama la función de búsqueda en la búsqueda funcionar en cualquiera de la mitad de la matriz. Vamos a cubrir la recursividad un poco más adelante en el curso. Pero no saben que es una opción si usted desea probar.