[REPRODUCCIÓN DE MÚSICA] 

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 se implementa como un búsqueda lineal, pero se puede hacer mucho mejor que eso. La búsqueda lineal se implementa en O de tiempo n, 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 vamos a ver un ejemplo. Dada una matriz de valores, el pajar, vamos a estar buscando para una aguja. Y en este ejemplo, el número entero tres. 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 una agenda para el medio página en la semana cero. 

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, ya que tres, 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. Así que estás en lo cierto límite puede apretar la búsqueda sale un poquito más, y así sucesivamente y así sucesivamente hasta a encontrar su aguja. 

Entonces, ¿qué hace el pseudocódigo parece? Bueno, mientras que todavía estamos mirando a través de la lista y aún así tener elementos para Buscar en, tomamos la mitad de la lista, y comparar ese 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 descartar la mitad derecha, 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 ha encontrado su aguja todavía, entonces usted return false porque la aguja definitivamente no se encuentra en el pajar. 

Ahora, una cosa aseada sobre este pseudocódigo en búsqueda binaria es que puede ser interpretarse 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 tarde en el por supuesto, pero sí sabemos que se trata de un opción si desea probar. 

Ahora echemos un vistazo a clase. Ordenar toma una matriz y el número entero n, que es el tamaño de la matriz. Ahora bien, hay varios tipos diferentes de las clases, y se puede ver en algunos pantalones cortos para demostraciones y explicaciones. El tipo de cambio de nuestra función de clasificación es nula. Así que eso significa que no vamos para devolver cualquier matriz de ordenación. Estamos realmente va a cambiar la misma matriz que se pasó a nosotros. 

Y eso es posible porque las matrices son pasan por referencia en C. Ahora vamos a ver más sobre esto más adelante, pero el diferencia esencial entre pasar en algo así como un entero y pasa en una matriz, es que cuando se pasar en un entero, C es sólo va a hacer una copia de ese entero y pasar a la función. No se modificará la variable original una vez que la función ha terminado. Con una matriz, por otro lado, es no va a hacer una copia, y usted en realidad ser la edición de la sí muy array. 

Así que un tipo de especie es el tipo de selección. La ordenación por selección Funciona a partir de las Al principio, y luego iterar una y encontrar el elemento más pequeño. Y entonces cambias que los más pequeños elemento con la primera. Y entonces usted se mueve al segundo elemento , Buscar la siguiente más pequeña elemento, y luego de intercambio que con la segundo elemento de la matriz, ya el primer elemento ya está ordenado. Y entonces usted continúa para cada elemento en la identificación de la más pequeña valor y el trueque de un vistazo. 

Para I es igual a 0, el primer elemento a n menos 1, vas a comparar cada valor siguiente después de eso y encontrar el índice del valor mínimo. Una vez que encuentre el índice de valor mínimo, usted puede cambiar el valor de la matriz mínimo y variedad I. 

Otro tipo de especie que pueda implementar es la ordenación de burbuja. Así se repite burbuja ordenar más de la lista la comparación de los elementos adyacentes y el intercambio de los elementos que están en el orden equivocado. Y de esta manera, el elemento más grande burbujeará hasta el final. Y la lista se ordena una vez más elementos se han intercambiado. 

Así que estos son dos ejemplos de una especie algoritmos que se pueden implementar para el programa de búsqueda. Una vez que termine de ordenar y tienes Búsqueda hecho, haya terminado. Mi nombre es Zamyla, y esto es CS50. 

[REPRODUCCIÓN DE MÚSICA]