>> [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]