JASON HIRSCHHORN: Bienvenido a la semana tres, todo el mundo. Tenemos una concurrida pero apasionante sección por delante de nosotros. Así que en primer lugar, porque hemos hecho algunos avanzar en el curso, pero todavía tienen una gran cantidad de aprendizaje más que hacer, estoy va a aparecer ustedes algunos recursos que debe llegar a ser increíblemente útil ya que no sólo se acerca a su boletines de problemas, sino también a digerir todos el material que le damos chicos en conferencias y pantalones cortos y sección. A continuación vamos a pasar los primeros 20 a 25 minutos de la sección repasando GDB, que usted puede o no puede tener utiliza en este punto, pero es una herramienta increíblemente útil que le ayudarle a depurar sus programas. Muchos de ustedes pueden haber utilizado printf en el medio de su programa de averiguar lo que equivalía a una variable. GDB es incluso mejor que printf y no arruinar su código porque ejecutarlo en un archivo ejecutable. Así que vamos a repasar los 10 más útiles los comandos que necesita para el IAE, y estamos va a ir en un ejercicio juntos para en el problema de establecer tres y más allá, que puede usar GDB para ayudar a depurar sus programas. Y, por último, vamos a repasar algunos clasificación y búsqueda de algoritmos que has visto en clase, y estamos ir a la realidad de código, no sólo pseudocódigo, pero el código binario de búsqueda, ordenamiento de burbuja, y la selección de clasificación. Así que en primer lugar, quiero ir sobre los recursos. Esta es una lista extensa, y es pequeña fuente, porque tenía mucho que encajar aquí. Pero estos no sólo le va a ayudar, de nuevo, con los boletines de problemas y información para digerir que aprendió, pero sin duda, llegado el momento concurso, éstos se ser increíblemente útil. Así que en primer lugar, la ponencia señala. Si usted va a cs50.net/lectures y desplazarse a la semana y un día específico, verás que hay notas para cada dar una conferencia, la cual no es más que una transcripción, pero una versión editada de lo que fue cubierto en la conferencia con el código de fragmentos y otras cositas útiles. Recomiendo ir sobre aquellos. Y entonces, así, no hay código fuente disponible de cada conferencia. Y de nuevo, estas diapositivas también estarán disponible en línea en cs50.net/sections esta tarde. Así segundos son los cortos cada semana que temas de cobertura, por lo general de 5 a 15 minuto de longitud. Y aquellos con suerte le dará una gran introducción a diferentes temas. En tercer lugar - y esto es nuevo este años - es study.cs50.net. Si usted no ha comprobado hacia fuera, yo altamente recomendable que lo haga. Tienes la oportunidad de elegir un tema. Tenemos docenas de temas sobre los que hay. Así, por ejemplo, tienes que elegir las funciones. Le da algunas diapositivas y toma nota de las funciones. Esas son en realidad las diapositivas que TFS se les anima a usar durante nuestra presentaciones en la sección. También hay consejos y trucos para hacer frente con funciones, y hay problemas prácticos que ayudan a trabajar con funciones. También le damos enlaces a la corta en funciones y las veces en las que las funciones han surgido en la conferencia. Así study.cs50.net estrenar esta año, un recurso fantástico. A continuación, tengo el hombre, que es el manual de comando que se puede ejecutar en el línea de comandos. Así que si usted tiene alguna pregunta acerca de un comando, por ejemplo, Rand, que nos encontrado la semana pasada durante la sección y es probable que haya encontrado en su problema ajusta al pasar por el generar código, pero si escribe man rand, obtendrá la página que te dice todo sobre rand. Le da lo que se necesita, la parámetros que se necesita, así como el retorno tipo y una breve descripción de esa función. Así que echa un vistazo a rand. Puede ser un poco prolijo y confuso, así que a veces me parece que simplemente buscar en Google lo que quiero saber es la mejor manera de encontrar la respuesta. Así que la práctica con Google. Ser bueno en Google. Se convertirá en su mejor amigo. Además de Google, si usted no puede encontrarlo en Google, cs50.net/discuss, es el foro de discusión. Es probable que si usted tiene una pregunta, una de sus más de 700 compañeros también tiene que cuestión y pudo haber pedido ya en el discutir foros y haga que sea contestada. Así que si usted tiene una pregunta común o usted tiene una pregunta que usted piensa tal vez otras personas podrían haber quedado en, echa un vistazo a cs50.net/discuss. Finalmente, los dos últimos, si quieres hablar con un ser humano real, oficina horas de lunes a viernes. También hay horas de oficina en línea para los estudiantes de extensión. Y por último pero no menos importante, mí, signo de exclamación. Todos ustedes tienen mi información de contacto. Si necesitas algo, por favor, nunca dude en ponerse en contacto conmigo. Siempre siéntase libre de hacerlo. Muy pocos de ustedes me han agregado en Gchat, por lo que ha sido decepcionante, pero espero que eso cambiará entre este y el próximo apartado. Cualquier pregunta hasta ahora sobre los recursos? Grande. Por último, otro tapón para retroalimentación, sayat.me/cs50. Usted me puede dar información anónima de cómo lo estoy haciendo. Eso fue muy útil la semana pasada. Tengo un par de comentarios de ustedes justo después de la sección, además de otros estudiantes que lo vieron durante la semana, y era increíblemente servicial. Voy a tratar de limitar mi uso de la palabra "dulce", pero yo te mostraré mi entusiasmo y emoción en otras formas. Pero había otra adicional evaluaciones sustantivas, ambas ventajas y delta. Así que por favor, le doy ustedes retroalimentación en sus boletines de problemas. Siéntase libre de dar su opinión en mi enseñanza. Estoy aquí para ustedes. Grande. Eso es todo lo que tengo para la primera sección. ¿Alguien tiene alguna preguntas hasta ahora? Y tengo una nota para el centro de control. Estudiantes de extensión me han contactado a diciendo que no van a obtener cualquier archivo de audio, pero eso está fuera de mi alcance para solucionar. Así que espero, que obtiene resuelto en breve. Si estás viendo en línea, hi, pero usted no me puede oír. Así que primero, vamos que pasar por el BGF. GDB, como ya he insinuado antes, es una herramienta de depuración mucho mejor que printf. Así que para empezar con GDB, chicos, si quiere abrir su aparato y tomar el archivo que envié a usted antes - este archivo también será disponible en línea en un poco - y ejecutar BGF. / el nombre del archivo. En primer lugar, por supuesto, usted tiene que compilar presentar porque BGF sólo funciona en archivos ejecutables. Pero si alguna vez desea iniciar GDB, el primero que se hace, ejecuta GDB. / César. Así que ese es el nombre del programa que estamos va a ir con él en estos momentos. Así que voy a escribir hacer César, que me dará un archivo ejecutable aquí resaltada en verde. Y luego me voy a correr GDB. / Cesar. Y ahí lo tienes. Ya ves que tenemos un poco de texto diciéndome sobre la versión de GDB, dándome alguna información sobre la garantía, y luego tienen el símbolo del PIB, lo que parece algo de que nuestra petición de la línea de comandos, pero ya ves que está abierto paren, GDB, cerca paren. Antes de continuar y depurar el archivo que envié a todos ustedes, vamos a ver algunos comandos útiles para que tengan un sentido de lo que vamos a cubrir. Estos comandos están listados aquí, en el orden en el que por lo general los uso. Así que empiezo mi programa ejecutando GBD. / Nombre del programa, en este caso, César. Y entonces lo primero que hago 99,9% de las veces es malo tipo de rotura. Eso establece un punto de quiebre en el principal. En esencia, lo que está haciendo allí es el programa que va a parar en principal para que pueda empezar a examinarlo línea por línea, en lugar de correr todo el camino a través. Usted puede romper en diferentes puntos su código, pero principal es generalmente un buen lugar para empezar. El siguiente comando Corro es un negocio. Esto comienza el programa en ejecución, y si usted necesita para entrar en la línea de comandos argumentos, lo ejecuta ese comando. Ejecutar con los argumentos. Así que ya que vamos sobre una versión de C, que es el programa que ustedes escribió para el conjunto de procesadores de dos - éste, por supuesto, tiene algunos errores en lo que es de esperar que encontraremos - vamos a correr correr con algunos comandos argumentos de la línea, porque César, como ustedes saben por el problema establece las especificaciones, toma un poco de argumentos de la línea de comandos. El siguiente par de comandos, el siguiente uno se llama en realidad siguiente. Este toma usted línea por línea a través de su programa. Así golpear n luego Enter te lleva a la siguiente línea, la ejecución de la línea anterior. Paso no sólo le lleva a la siguiente línea, pero te lleva al interior de funciones. Así que si usted ha escrito una función en el código o si desea explorar un a i, por ejemplo, usted puede golpear s, y en lugar de ir a la siguiente línea de el archivo que estás pasando Ahora, usted realmente paso en esta función y ver su código. Lista muestra, muy fácil de usar formato, el 10 o así las líneas alrededor de donde se encuentra actualmente en el código así que usted puede ver realmente el archivo en lugar de tener que cambiar hacia atrás y hacia distintos puntos de vista. Imprimir es como printf, como su nombre lo indica. Eso demuestra lo que es igual a una variable. Lugareños información es realmente útil. Se trata de una versión especial de impresión. Información lugareños te muestra todos los locales las variables, todas ellas imprime hacia fuera para usted que están actualmente disponibles. Así que en general, en lugar de tener que imprimir las cuatro variables que estoy curiosidad sobre si estoy en un bucle, por ejemplo, acabo de escribir información locales, y me lo que mi contador te muestro iguales, así como la matriz que soy trabajando en iguales. Finalmente, continúe. Escribiendo pausa que se detiene en el punto de ruptura. Se puede caminar a través de la línea de línea con la próxima y paso. Continuar ejecuta el programa de su próxima romper punto o hasta la finalización si no hay más puntos de quiebre. Desactivar elimina puntos de quiebre si decidió romper en la principal era inapropiada, quieres establecido en otro lugar. Y, finalmente, q, abandonado, se sale de GDB. Así que este programa,. / César, vamos mirar a través de este momento y van a usar GDB para encontrar los errores en este programa. Me encontré este programa antes con Compruebe el 50, y yo tengo uno ceño. Todo lo que existía, lo recopiló, se pasado una gran cantidad de las pruebas, pero para alguna razón, no pasó del quinto prueba, girando barfoo, todo en mayúsculas, en E-D-U-I-R-R, todo en mayúsculas, usando tres como una clave. Tengo bastante cerca. Me bajé por una letra. Así que hay algún pequeño error aquí. He mirado a través de mi código. Yo no podía entenderlo. Con suerte, ustedes pueden ayudarme averiguar lo que este error es. Así que ese es el error que estamos buscando. Vamos a pasar a GDB. Una vez más, me he encontrado GDB. / César, por lo que ahora estamos en el BGF. Y lo que es lo primero Lo que debería hacer? Yo sólo he entrado GDB. Alguien me da una buena comando para entrar. ESTUDIANTE: Romper principal. JASON HIRSCHHORN: Romper principal. Fantástico. Escribamos que pulg Ustedes pueden ver aquí o seguir a lo largo de sus ordenadores. Main Break, y verás un punto de ruptura se fijó en - me da un poco de dirección de memoria extraño, y también me da el número de línea. Si tuviera que mirar hacia atrás en este archivo, Me daría cuenta de que la principal ocurrido en la línea 21. ¿Qué debo ejecutar el siguiente? ¿Está mi programa en ejecución? No. Entonces, ¿qué debería funcionar ahora? ESTUDIANTE: Run. JASON HIRSCHHORN: Run. ¿Debo correr correr, o debería Añado algunas otras cosas en? ESTUDIANTE: Ejecutar con el argumento. JASON HIRSCHHORN: Ejecutar con los argumentos de comandos. Y ya que estoy depuración de una muy específica caso, que debería entrar en ese argumento de la línea de comandos. Así que me voy a hacer correr tres, que es, de nuevo, la salida que recibí de Check 50. Programa de inicio. Vamos a través de un par de líneas. Ahora verás que estamos en la línea 21. ¿Cómo sé que estamos en la línea 21? Porque si miras a la izquierda de mi ventana de terminal, hay que dice la línea 21. Y eso me da, en realidad, la código que se encuentra en la línea 21. Así que me equivoqué antes. Principal no es en realidad en la línea 21. Principal es un par de líneas por encima de 21. Pero en la línea 21, que es donde estamos rompiendo. Esta línea de código tiene aún no ejecutado. Eso es importante. La línea que se ve no tiene sido ejecutado todavía. Esa es la siguiente línea de código usted está a punto de ejecutar. Así que la siguiente línea, como ustedes son probablemente está familiarizado con, es este condiciones comprobación para ver si tengo entrado en un argumento de línea de comandos. Y una de i, lo que es el segundo parte de que va? ¿Qué es un ai? ESTUDIANTE: Si lo cambia a un número entero. JASON HIRSCHHORN: ¿Lo sientes? ESTUDIANTE: Está cambiando la argumento en un entero. JASON HIRSCHHORN: Así que una de i cambios arg v1 de una cadena a un entero. Y entonces ¿cómo es de cheques? ESTUDIANTE: Si hay una segunda argumento de línea de comandos, a un lado de ejecutar el programa. JASON HIRSCHHORN: Y lo que es la segunda mitad de este Comprobar expresión booleana? Esta parte de aquí, una de i? ESTUDIANTE: Si es negativo. JASON HIRSCHHORN: Asegurarse de que? ESTUDIANTE: Asegurarse de que es, de hecho, positiva. JASON HIRSCHHORN: Exactamente. Esta es la comprobación para ver si es negativo, y si es negativo, lo tener una sensación de la próxima línea de fuerza ser yo gritando en el usuario. Así que vamos a golpear fin de ejecutar esta línea. No vemos que la línea que los chicos quizás esperaba ver a gritar a la usuario y luego volver, porque esta línea no se ha ejecutado. Entré 3. Así lo hice, de hecho, introducir dos comandos argumentos de la línea, y 3 es mayor que cero. Así que vimos esa línea, ejecutamos, pero no nos pisamos dentro de la condición if. Así que ahora, al lado, veo que estoy estableciendo clave int es igual a una i arg v1. Así que eso es crearme una clave variable. Así que si imprimo clave en este momento, porque que le permite ver la valor dentro de la variable, clave es igual a 47. Eso es raro, pero por supuesto, eso es porque no lo he hecho ejecutado esa línea aún. Así que ahora si le pego n, ejecutar esa línea, y hacer tecla de impresión, clave será igual a 3, que es lo que esperamos que sea igual a. Así que de nuevo, en el BGF, la línea que Veo que no has ejecutado todavía. Usted tiene que golpear n o s o un número de otros comandos a realidad ejecutar esa línea. Tecla Imprimir. La llave está en 3. Hasta ahora, todo bien. String es texto plano. Vamos a ejecutar esa línea. Me estoy poniendo una cadena de usuario. Vamos a ver en mi Check 50, I introducir barfoo mayúsculas, por lo eso es lo que voy a entrar. Si ahora puedo imprimir texto plano. Verás que es igual a una cadena. Me da un poco de otra hexadecimal raro número, pero lo hace en hecho de decir que mi cadena es barfoo. Si yo quería ver lo que igualó clave en este punto, ¿cómo podría comprobar llave? ESTUDIANTE: tecla Imprimir. JASON HIRSCHHORN: tecla Print, exactamente. Y de hecho, hay un acceso directo. Si te cansas de escribir de impresión, que puede simplemente escribir p. Así tecla p hace exactamente lo mismo. Y de nuevo, yo lo veo es igual a 3. Si quisiera saber lo tanto clave y barfoo igualó al mismo tiempo pero yo estaba cansado de escribir cada uno de forma individual, que podría escribir info lugareños. Eso me da igual claves 3. Texto sin formato es igual barfoo. También me da estas dos cosas raras en la parte superior, esta variable iy esta variable n. Esos son realmente existente en mi programa principal. No los hemos encontrado, sin embargo, sino como una vista previa, los existir en mi bucle for. Así que ahora mismo, que equivalen a un poco raro números porque no han sido inicializan todavía, pero que todavía existen en la memoria, por lo que sólo están fijados a algún valor de basura. Pero sí vemos clave en la llanura texto allí. Así que voy a ejecutar esta línea, la línea 34, el bucle para. Vamos a saltar en el bucle pulsando n. Y estamos dentro del bucle. Estamos en nuestro primer cheque. Y una vez más, este tipo de deben buscar familiar para usted, porque se trataba de un Programa de César que fue escrito, pero de nuevo, tiene algún tipo de error. Y ahora, si lo hago de información locales, porque soy dentro de ese bucle, verás que i es igual a cero, ya que esperamos. Eso es lo que nos propusimos a e inicializado que en el bucle for. n es igual a 6. Eso también hace sentido porque establecemos al strlen de texto sin formato. Así que me gusta hacer información locales o de impresión a la variable a menudo para asegurarse de que todo es siempre lo Espero que para igualar. En este caso, todo está lo que espero que sea igual a. Así que vamos a empezar a moverse a través de este bucle. La línea que estoy es la línea 36, ​​si llanura texto i es mayor que una y la llanura texto i es menor que o igual a z. Sé que mi problema no es con mi primera carta, que es con la segunda letra. Si miramos hacia atrás a la llegada 50, B va a E bien. Estoy tomando la A y dejarlo como una A, no la cambia por D. Así algo anda mal con la segunda letra. Así que me voy a mover en un segundo. Pero si yo quería comprobar lo sencillo texto que igualó en este particular, caso, yo creo que debería ser qué? ¿Qué debería de texto plano que ser igual en esta primera ronda a través del bucle? ESTUDIANTE: Zero? JASON HIRSCHHORN: Texto simple de I? Así debería ser capital B. Yo, por supuesto, es igual a cero, pero el texto sin formato soporte de abrazadera cerrada es igual a cero B porque las cadenas, como vimos la semana pasada, somos matriz, por lo que estamos recibiendo la primer carácter de eso. Así que de nuevo, si Imprimí texto plano de Yo, yo, de hecho, conseguir el carácter B. Y eso es limpio, ¿verdad? Yo en realidad no tengo texto plano I. Eso no es una de las variables que establecí o inicializado, pero puede imprimir a cabo toda una serie de cosas si desea. Pero vamos a pasar a través. Si texto plano I es mayor que A y texto plano I es menor que o igual a Z, que claramente es cierto porque tenemos una capital de B. Voy a correr algún comando en él. Vimos que las matemáticas la semana pasada, así que vamos a dar por sentado de que funciona correcto según Check 50. Estas llaves, el primero demostré que estaba saliendo de la si condición, el segundo uno mostró que me estoy saliendo del bucle for. Y ahora cuando golpeé A continuación, vamos a ver estamos de vuelta en el bucle de nuevo. Vamos a través de la para el bucle de nuevo. Vamos realmente paso en el segundo iteración del bucle y el tipo info lugareños. Así que estamos en la segunda iteración de nuestro bucle para. I es igual a 1, lo que esperamos. N es igual a 6, que esperamos. Es igual a la tecla 3, la cual esperamos. Y de texto sin formato, verás, es igual a EARFOO ahora, no más porque barfoo en nuestra iteración anterior, el B fue cambiado a una capital E. Así que estamos a punto para encontrar el problema, por lo que este es donde vamos a sumergirse en la depuración. Pero ¿alguien tiene alguna pregunta acerca de lo que hemos hecho hasta ahora? Fantástico. Así que estamos a punto de ejecutar esto si condición, soporte de texto plano Cerré soporte mayor que A y texto plano I menos de o igual a la Z. Pero antes Entro en eso, porque aquí es donde Sé que mi error es, quiero señalar fuera de texto sin formato de I. Así vamos a poner impresión. Lo hace igual al carácter A, de modo que parece hasta ahora, todo está bien y bueno. Así que espero que esta línea por mi lógica, esta línea debe ser verdad. Es una letra mayúscula. Pero si le pego n, nos damos cuenta de que este línea, de hecho, no se ha ejecutado. Salté a la otra persona si. ¿Por qué sucedió eso? ESTUDIANTE: Debido a que tiene su condición de texto plano es mayor que A, no es igual o mayor que. JASON HIRSCHHORN: Así que tuve mi texto plano I es mayor que A, no mayor que o igual a. Así que, claramente, la capital A no hizo desencadenar esta condición si, y lo hicimos no entrar en él, y lo hicimos no hacer el cambio necesario. Así que es eso, en realidad. Me di cuenta de mi error. Pudiera volver atrás en mi archivo de origen, cambiarla y actualizarla y Ejecute una comprobación 50 de nuevo. Pero vamos a ver, sólo por la pedagogía de bien, si sigo adelante. La otra persona si no se ejecuta bien, pero lo que en cambio es igual a es el comando eso no cambia. Por lo que no ha cambiado en absoluto, y si imprimir texto plano aquí, vamos a ver que va a través de ese bucle no lo hizo, de hecho, cambiar ese segundo carácter en absoluto. Es todavía un capital de A. Así que de nuevo, estamos depurando nuestro error. Nos dimos cuenta de que no había una lógica que falta. Y hemos depurado antes de tiempo antes realmente ejecutar esa línea, pero se habría dado cuenta si hubiéramos sólo Siguiente golpear y saltar a esa persona si, eso significa que que si la condición No era cierto. Nosotros no, de hecho, obtenemos el resultado que se esperaba. Así que nos podría haber sido incitado, tuvimos si no hubiéramos estado tan astuto, que mirar que si el estado y comprobar si, de hecho, nuestra condición debe evaluar a cierto en el contexto actual. Eso es todo para la depuración de este programa. ¿Alguien tiene alguna pregunta? ¿Qué comando podría golpear a dejar de GDB? P. ¿Y entonces le pedirá, sale de todas maneras? Sí o no. Voy a golpear sí, y te he dejado GDB. Así que fue una cartilla rápida de GDB. En realidad, en un escenario real, Hice esto en horario de oficina. Me GDBed este programa exacto en horas de oficina con un estudiante. Y si nos remontamos a los comandos que vimos antes, se utilizó ruptura principal, primero cosa que hicimos. Utilizamos carrera con los argumentos de línea de comandos, segunda cosa que hicimos. Utilizamos próxima mucho para mover nosotros a través de las líneas. Y de nuevo, la versión corta de la próxima es n. Eso está en los paréntesis en gris en la diapositiva. No usamos el paso, pero no lo hicimos necesariamente tienen que para este caso. Pero podríamos utilizarlo en un poco más tarde en la actualidad si se está depurando, por ejemplo, la búsqueda binaria cuando binario búsqueda se llama en una separada función, pero hay algún error con él. Vamos a querer entrar en la llamada a la búsqueda binaria y realidad depurarlo. Lista que no use ya sea porque teníamos un buen sentido de nuestro código, pero si ha querido tener una idea de lo que el código que estaba cerca, podía simplemente utilizo lista. Imprimir utilizamos, los locales de información que utilizamos. Continuar nosotros no necesitamos usar en este caso, tampoco tenemos que utilizar desactivamos, pero hicimos uso renunció. Una vez más, estos 10 mandamientos, practicarlas. Si usted entiende estos 10 mandamientos, usted debe estar preparado para depurar cualquier emitir con GDB. Así que vamos a seguir, una vez más, a la quid de la sección de hoy, repasando estos ordenación y búsqueda algoritmos. Antes de hacerlo, una vez más, cualquier pregunta, comentarios, inquietudes para GDB? Así es todo el mundo va a usar BGF en lugar de printf? Así que todo el mundo, por el amor de perpetuidad, todo el mundo asiente con su cabeza a la derecha ahora, así que voy a verte en horario de oficina y todos los TFS te verán y que van a decir, muéstrame cómo utilizar GDB, y podrás para mostrar, ¿no? Un poco? Tal vez con suerte. Genial. Así que vamos a pasar a ordenación y búsqueda. Vas a ver que tengo una lista ya ordenada para nosotros, pero eso no va ser el caso siempre. Así, en el conjunto de problemas de especificaciones para problema fijó tres, tienes pantalones cortos que se puede ver, y que en realidad le pregunta a ver esos pantalones cortos. También en la conferencia la semana pasada, fuimos muchos de estos algoritmos, así que estoy No va a pasar un tiempo en la clase va sobre estos algoritmos de nuevo o dibujo fotos para ver cómo se algoritmos funcionan. Una vez más, que la información que pueda volver a ver conferencia, o que la información es capturado extraordinariamente en los pantalones para estas búsquedas, todos que están disponibles en cs50.net. Así que en vez, lo que vamos a hacer es escribir estos programas. Tenemos un sentido, un modelo mental, de cómo trabajan, y así lo vamos hacer es codificar los de verdad. Vamos a convertir ese modelo mental, ese cuadro, si se quiere, en el código real. Y si fueras un poco confundido o nebuloso en el modelo mental, estoy totalmente de entender. No estamos realmente va a saltar al código inmediatamente. Así, mientras que este indicador en esta diapositiva pregunta a código de búsqueda binaria, y en realidad, una versión iterativo de búsqueda binaria, lo primero que Realmente quiero que hagas es escribir algo de pseudocódigo. Por lo que tiene este modelo mental de cómo los trabajos de búsqueda binaria. Tome una hoja de papel si tiene uno de fácil acceso, o abrir un editor de texto, y me gustaría a todo el mundo a escribir. Tomar cuatro minutos para escribir la pseudocódigo para la búsqueda binaria. Una vez más, pensar en ese modelo mental. Vendré por aquí si tiene preguntas y podemos dibujar la imagen fuera. Pero primero, antes de empezar la programación, Me gustaría escribir la pseudocódigo para búsqueda binaria así que cuando nos bucear, tenemos una cierta dirección como a donde debemos ir. ESTUDIANTE: ¿Podemos asumir el conjunto de valores que obtenemos ya está ordenado? JASON HIRSCHHORN: Así que para búsqueda binaria trabajar - excelente pregunta - que tomar en una ordenada matriz de valores. Así que supongamos que va a funcionar. Volveremos a esta diapositiva. Usted verá en púrpura de la función declaración es bool binary_search int valor, valores int, int n. Esto debería resultar familiar si has ya abordado o conseguido su las manos sucias con el conjunto de problemas. Pero ese es su declaración de la función. Una vez más, no debería tener que preocuparse por que tanto en este momento. Lo que realmente quiero hacer es tomar Cuatro minutos para binario pseudocódigo Buscar y, a continuación, vamos a ir más que como un grupo. Y voy a entrar en razón. Si usted tiene preguntas, por libertad para que levante la mano. ¿Por qué no te tomas dos minutos más para terminar el pseudocódigo? Sé que esto puede parecer ridículo que estamos gastando tanto tiempo en algo que ni siquiera es realmente en C, pero sobre todo para estos más algoritmos difíciles y problemas conjuntos que tenemos que averiguar, comenzando en pseudocódigo no preocuparse acerca de la sintaxis, sólo preocuparse la lógica, es increíblemente útil. Y de esa manera, no vas a resolver dos problemas muy difíciles a la vez. No eres más que centrarse en la lógica, y entonces usted se mueve en la sintaxis. Aceptar. Empecemos pasar por el pseudocódigo. He escrito aquí, binario Búsqueda pseudocódigo. Vamos a escribir esto en el abordar juntos. O lo escribiré y te voy a dar me las indicaciones que necesito. Entonces, ¿puede alguien darme la primera línea del pseudocódigo que escribió para la búsqueda binaria? Sí, Annie? ESTUDIANTE: Si bien la longitud de la lista es mayor que cero. JASON HIRSCHHORN: Mientras que la longitud de la lista superior a cero. Y una vez más, vemos algunos C-buscando cosas sintácticas de aquí. Pero la mayor parte de esto está en Inglés. ¿Alguien tiene alguna línea que ponen antes de esto en su pseudo-código? ESTUDIANTE: Obtiene un array de ordenar números. JASON HIRSCHHORN: Usted escribió "obtiene una matriz de números ordenados. "Per la declaración de la función, vamos a estar pasando una matriz de números ordenados. ESTUDIANTE: [inaudible]. JASON HIRSCHHORN: Así vamos a tener eso. Pero sí, si no teníamos eso, tendría que ordenar nuestra gama de números, porque la búsqueda binaria sólo funciona en arrays ordenados. Así, mientras que la longitud de la lista es igual a cero, estoy va a poner en algunas llaves para que se vea un poco más como C. Pero mientras, parece en un mapa while, por lo que dentro de este tiempo loop ¿Qué necesitamos para hacer por búsqueda binaria? Otra persona que no me ha dado una responder todavía, pero que escribió esto? ESTUDIANTE: Vaya a la mitad de la lista. JASON HIRSCHHORN: Tom. Ir a la mitad de la lista. Y la pregunta de seguimiento, lo que qué hacemos una vez que estemos en la mitad de la lista? ESTUDIANTE: Haga una revisión de si eso es el número que está buscando. JASON HIRSCHHORN: Excelente. Ve la mitad de la lista y comprobar si nuestro valor está allí - fantástico. ¿Alguien tiene algo más que era diferente a esto? Eso es exactamente correcto. Lo primero que hacemos en la búsqueda binaria es ir a la mitad de la lista y comprobar para ver si nuestro valor está ahí. Así que supongo que si nuestro valor es allí, ¿qué hacemos? ESTUDIANTE: Volvemos a cero [inaudible]. JASON HIRSCHHORN: Sí, si nuestro valor está ahí, lo encontramos. Así que podemos decir de alguna manera, sin embargo, esto función se define, le decimos al usuario lo encontramos. Si no está allí, sin embargo, eso es donde esto se complica. Así que si no está allí, alguien que estaba trabajando en la búsqueda binaria o tiene una idea ahora, ¿qué hacemos? ESTUDIANTE: Pregunta. JASON HIRSCHHORN: ¿Sí? ESTUDIANTE: ¿Es la matriz ya ordenada? JASON HIRSCHHORN: Sí, estamos asumiendo la matriz ya está ordenado. ESTUDIANTE: Entonces usted tiene que comprobar si el valor que usted ve es mayor que el valor que usted quiere, usted puede moverse a la mitad de la otra mitad. JASON HIRSCHHORN: Entonces, si el medio de la lista es mayor que lo que estamos buscando, entonces nosotros qué? Realizamos movimientos interiores de dónde? ESTUDIANTE: ¿Quieres ir a la mitad de la lista con números más bajos que eso. JASON HIRSCHHORN: Así que vamos a llamar a que la izquierda. Así que si en medio es mayor, podemos buscar la mitad izquierda de la lista. Y luego por la búsqueda, lo que Qué quiero decir con la búsqueda? ESTUDIANTE: [inaudible]. JASON HIRSCHHORN: Vamos a la media. En realidad nos repetimos esta cosa. Volvemos a través de nuestro bucle while. Te voy a dar el último - otra cosa, si, en medio es menos de lo que lo que hacemos, ¿qué hacemos aquí? ESTUDIANTE: Ir a la derecha. JASON HIRSCHHORN: Búsqueda de la derecha. Esto se ve bien, pero ¿alguien tiene nada de lo que puede estar presente o cualquier otra cosa que se pone en su pseudo-código? Así que esto es lo que tenemos hasta ahora. Mientras que la longitud de la lista es mayor de cero, vamos a ir a la mitad de la lista y comprobar si nuestro valor está ahí. Si el medio es mayor, vamos a buscar a la izquierda, más si el medio es menos, vamos a buscar la derecha. Así que todos hemos tenido alguna familiaridad con los términos que usamos en informática y las herramientas que tienen. Pero usted ya notará que éramos hablando en Inglés, pero encontramos un Muchas cosas que parecían un mapa a partir de herramientas que tenemos en nuestra caja de herramientas de codificación. Así que de buenas a primeras, no estamos va a codificar en realidad todavía. ¿Qué es lo que vemos aquí en Inglés que los mapas a cosas que podemos escribir en C? ESTUDIANTE: While. JASON HIRSCHHORN: While. Así que este tiempo aquí mapas sobre a qué? ESTUDIANTE: Un bucle while. JASON HIRSCHHORN: Un bucle while? O probablemente, más en general, un bucle. Queremos hacer algo una y otra vez. Así que vamos a codificar un bucle. Y ya sabemos, porque hemos hecho esto un par de veces y nos tienen un montón de ejemplos por ahí, cómo en realidad para escribir este índice para un bucle. Así que debería ser bastante fácil. Debemos ser capaces de conseguir que comenzado con bastante rapidez. ¿Qué otra cosa es lo que vemos aquí? ¿Qué otras estructuras de sintaxis, las cosas que estamos familiarizados en C, ¿nos ya tener un sentido del Based fuera de las palabras que utilizamos? Sí, Anna? [Inaudible] es broma. Anna, adelante. ESTUDIANTE: Si y más. JASON HIRSCHHORN: Si y otra cosa - aquí mismo. Entonces, ¿qué los ve? ESTUDIANTE: Un if-else. JASON HIRSCHHORN: Sí, condiciones, ¿no? Así que probablemente tendrá que escribir algunas condiciones. Y de nuevo, aunque quizás confuso al en primer lugar, por lo general tienen un sentido ahora de cómo escribir las condiciones y la sintaxis para las condiciones. Y si no lo hacemos, sólo miramos el sintaxis de condiciones, cortar y pegar que, debido a que sabemos que necesitará una condición aquí. Cualesquiera otras cosas que vemos ese mapa en cosas que podríamos necesitar hacer en C? Sí, Aleha? ESTUDIANTE: Esto puede ser obvio, por sólo la comprobación si un valor es igual a algo. JASON HIRSCHHORN: Entonces, ¿cómo comprobamos y - a fin de ir a la mitad de la lista y comprobar si nuestro valor está allí? ¿Cómo hacemos eso en C? ¿Cuál es la sintaxis para eso? ESTUDIANTE: Es igual, es igual. JASON HIRSCHHORN: igual, es igual. Así que este cheque es, probablemente, va ser un signo de igual, es igual. Así sabremos lo que necesitamos que en algún lugar. Y, de hecho, sólo en escribirlo, vemos esas otras cosas. Vamos a tener que hacer un poco de operadores de comparación en allí - fantástico. Así que en realidad se parece, en términos un grande, no hemos escrito palabra de código de C todavía. Pero tenemos el modelo mental hacia abajo a través de conferencias y los pantalones cortos. Escribimos pseudo-código como un grupo. Y ya tenemos el 80% si no se 90% de lo que necesitamos hacer. Ahora, sólo tenemos que codificar , lo que de nuevo, es un problema no trivial de resolver. Pero al menos estamos atrapados en la lógica. Por lo menos ahora, cuando vamos a las horas de oficina, Lo que puedo decir, yo sé lo que necesito hacer, pero puede usted recordar me de la sintaxis? O incluso si las horas de oficina están llenas, usted ¿Puede Google para la sintaxis, en lugar que estar atrapado en la lógica. Y de nuevo, en lugar de tratar de resolver la lógica y los problemas de sintaxis todos a la vez, a menudo es mucho mejor romper esos dos problemas difíciles apagado en dos más manejables y hacer el pseudo-código primero y luego el código en C. Así que vamos a ver lo que hice para el pseudo-código antes de tiempo. Mientras que la longitud de la lista es mayor que cero, mira la media de la lista. Si el número se encuentra devuelto cierto, otra cosa si el número más alto, búsqueda izquierdo. Porque si el número más bajo, búsqueda derecho, devolver false. Así que se ve casi idéntico, si no casi idéntica a lo que escribimos. En realidad, Tom, lo que dijiste en primer lugar, romper el medio de la lista y si número que se encuentra en dos estados es en realidad lo que hice. Yo los he combinado allí. Yo debería haber escuchado a que la primera vez. Así que ese es el pseudo-código que tenemos. Si quieres ahora, lo siento, vaya De vuelta a nuestro problema inicial. Del código binary.c Let. Así implementar una versión iterativa de búsqueda binaria utilizando el siguiente declaración de la función. Y no es necesario para copiar hacia abajo por el momento. De hecho voy a abrir hasta aquí binary.c. Así que no es la declaración de la función en el centro de la pantalla. Y verás que tomé el pseudo-código a partir de mis lados, pero casi idéntico a lo que escribimos, y poner eso por usted. Así que ahora, vamos a tardar cinco minutos para codificar esta función. Y de nuevo, si usted tiene cualquier pregunta, levantar la mano, que me haga saber, voy a entrar en razón. ESTUDIANTE: [inaudible]. JASON HIRSCHHORN: Así que tomó el binario definición de la búsqueda en la Arriba, en la línea 12. Eso es lo que tengo para mi diapositiva. Y entonces todo este pseudo-código que acabo de copiar y pegar de la diapositiva, pseudo-código de diapositivas. Todavía no estoy oyendo [inaudible]. Así que si usted ha terminado su aplicación, quiero comprobarlo. Les envié un correo electrónico el archivo helpers.h anteriormente en esta clase. Y estará disponible en línea, así para su descarga para observar a la gente esta vez la sección retrasado. Y acabo de utilizar la distribución genérica código de pset3. Así que tomé find.C, usar mi archivo helpers.h en lugar del archivo helpers.h que es dado en el código de distribución. Y tuve que hacer otro cambio en find.C en lugar de llamar simplemente búsqueda, llamar binary_search. Así que si quieres probar el código, saben que así es como se hace. De hecho, cuando vamos a estar corriendo este código en estos momentos, acabo de hacer una copia de mi directorio pset3, de nuevo, intercambia los archivos de ayudantes y luego hizo que cambiar en find.C para llamar binary_search en lugar de simplemente buscar. JASON HIRSCHHORN: Si. ¿Tienes una pregunta? ESTUDIANTE: No importa. JASON HIRSCHHORN: No se preocupe. Bueno, vamos a empezar. Vamos a codificar esto como un grupo. Una nota aparte. De nuevo, esto es, puede ser fácilmente intercambiado por Problemas de Tres. Tengo mi archivo helpers.h que, en lugar que el helpers.h se nos da, declara búsqueda binaria, burbuja ordenar y ordenación por selección. Y en find.c te darás cuenta en línea, ¿qué es eso, la línea 68, que llamamos binario en lugar de buscar en esta categoría. Así que de nuevo, el código que se encuentra disponible en línea o el código que son creando en estos momentos se puede intercambiar fácilmente por p el set 3 para comprobarlo. Pero primero, vamos a código de búsqueda binaria. Nuestra declaración de la función, volvemos un bool. Tomamos un entero llamado valor. Tomamos una matriz de enteros llamado valores, y tomamos n ser el tamaño de la matriz. En la línea 10, aquí, tengo aguda incluyen stdbool.h. ¿Alguien sabe por qué está ahí? Entonces, ¿qué esa línea de código hace? ESTUDIANTE: Le permite utilizar un tipo de retorno void. JASON HIRSCHHORN: Exactamente. ESTUDIANTE: ¿O es una biblioteca que permite utilizar un tipo de retorno void. JASON HIRSCHHORN: Así que la aguda incluyen line stdbool.h me da un poco de definiciones y declaraciones de las cosas que me permite utilizar en esta biblioteca. Así que entre los que está diciendo que no hay este tipo bool llama, y ​​puede ser verdadero o falso. Así que eso es lo que hace esa línea. Y si yo no tenía esa línea, lo haría tener problemas para escribir este palabra aquí, bool, justo ahí. Exactamente derecha. Así que necesito que en este código. Aceptar. Así que esto, de nuevo, es un proceso iterativo versión, no una recursiva. Así que vamos a empezar. Vamos a empezar con esta primera línea de código de pseudo. Y es de esperar, lo haremos - o no es de esperar. Vamos a ir alrededor de la habitación. Vamos a ir línea por línea, y yo te ayudaremos a determinar la línea que necesitamos para escribir primero. Así, mientras que la longitud de la lista es mayor que cero. Vamos a empezar en la parte delantera. ¿Qué línea debo escribir aquí, en el código? ESTUDIANTE: Si bien el paréntesis n es mayor que 0. JASON HIRSCHHORN: Mientras n es grande que 0. Por lo tanto n es el tamaño de una lista, y estamos comprobando si - [VOCES interponiendo] JASON HIRSCHHORN: - ¿Cómo? ESTUDIANTE: ¿Cómo sabemos que n es el tamaño de la lista? JASON HIRSCHHORN: Lo siento. Por la especificación pset, la búsqueda y ordenar las funciones que necesita para escribir, n es el tamaño de la lista. Me olvidé de explicar que aquí. Pero sí. n es el tamaño de la lista, en este caso. Así, mientras que n es mayor que 0. Aceptar. Esto puede resultar un poco problemático sin embargo, si las cosas siguen. Porque vamos a seguir para conocer la tamaño de la lista lo largo de este función, pero dicen que partimos con una serie de 5 números enteros. Y vamos a través y no tenemos ahora reducido a una matriz de 2 enteros. Cuál 2 enteros es eso? El tamaño es de 2 ahora que queremos a ver, pero que 2 es eso? ¿Eso tiene sentido, esa pregunta? Aceptar. Se lo preguntaré de nuevo. Así que empezamos con este conjunto de 5 enteros, y n es igual a 5, ¿no? Vamos a realizar aquí. es probable que cambiaremos el tamaño, derecha, como las cosas siguen. ¿Qué es lo que decimos que queremos hacer. No queremos buscar lo llena de nuevo. Así que digamos lo cambiamos a 2. Tomamos la mitad de la lista que es raro. Tan apenas escoja 2. Así que ahora n es igual a 2. Pido disculpas por la mala marcadores de borrado en seco. ¿Cierto? Y estamos buscando a través de la lista de nuevo con una lista de tamaño 2. Bueno, nuestra gama es todavía de tamaño 5. Nosotros decimos que sólo queremos buscar 2 puntos en el mismo. Así que 2 puntos son esos? ¿Eso tiene sentido? ¿Son los que quedan 2 puntos? ¿Son las correctas 2 puntos? ¿Son los medios 2 puntos? Hemos roto el problema hacia abajo, pero En realidad no sé qué parte de el problema que todavía estamos viendo, sólo por tener estas 2 variables. Así que necesitamos un poco más y luego, mientras que n es mayor que 0. Necesitamos saber dónde está ese n es en nuestra gama actual. Así que ¿alguien tiene un cambiar a esta línea? La mayor parte de esta línea es perfectamente correcto. ¿Hay otra adición? ¿Podemos cambiar algo que n que esta línea un poco mejor? Mm-hm? ESTUDIANTE: ¿Se puede inicializar una variable como la longitud de n que va a continuación, puede utilizar más adelante en la función? JASON HIRSCHHORN: Así inicializar una longitud variable a N, y usamos esa tarde? Pero entonces nos actualizamos longitud y aún con este problema en el que reducir la duración de nuestro problema, pero nunca se sabe donde, en realidad, que la longitud de los mapas en. ESTUDIANTE: ¿No es el que va a pasar más tarde, cuando usted está diciendo, busca a la izquierda, buscar ¿no? Vas a ir a una diferente área de su - JASON HIRSCHHORN: Vamos a ir a un área, pero ¿cómo sabemos que han de ir? Si sólo tenemos la matriz y esto n, ¿cómo sabemos dónde ir a la de la matriz. En el fondo, ¿no? ESTUDIANTE: ¿Tiene usted, como, una menor atado y una variable de cota superior o algo así? JASON HIRSCHHORN: OK. Así que esta es otra idea. En lugar de simplemente hacer el seguimiento de la tamaño, hacemos un seguimiento de la menor y variable de cota superior. Entonces, ¿cómo se calcula el tamaño de un límite inferior y límite superior? [VOCES interponiendo] JASON HIRSCHHORN: Resta. Y también hacer el seguimiento de la menor atado y límite superior de dejarnos saber, estamos buscando estos dos? ¿Estamos buscando a estos dos aquí? ¿Estamos buscando a los dos del medio? Probablemente no es el centro de los dos, porque esto, de hecho, es la búsqueda binaria. Pero ahora vamos a ser capaces de obtener el tamaño, sino también de los límites de la matriz. En esencia, si tenemos nuestro gigante guía telefónica, que rasgar por la mitad. Ahora sabemos que cuando más pequeño libreta de teléfonos es. Pero no estamos realmente rasga la guía telefónica por la mitad. Todavía tenemos que saber dónde está el nuevos límites de nuestro problema es. ¿Alguien tiene alguna pregunta acerca de eso? ¿Sí? ESTUDIANTE: ¿Funcionaría mediante la creación de un variable i, que entonces apenas muevo la posición de i con respecto a su posición actual, y la longitud, n? JASON HIRSCHHORN: ¿Y qué es i? ESTUDIANTE: Como he de ser como una especie de - Al igual que usted inicializa i para ser el posición media de la matriz. Y luego, si el valor en la posición i en el medio de la matriz en encontrado que ser menor que el valor que usted necesita, i ahora se convierte en la longitud de la matriz, más el valor de i dividido por 2. Al igual, ver, usted cambia de i - JASON HIRSCHHORN: Así es. ESTUDIANTE: - hasta el - JASON HIRSCHHORN: Así que estoy casi positivo que va a funcionar. Pero el punto es, que necesita dos piezas de información aquí. Usted puede hacerlo con principio y fin, o puede hacerlo con el tamaño, y luego algún marcador. Pero usted no necesita dos piezas de la información aquí. No se puede llegar a funcionar con sólo uno. ¿Eso tiene sentido? Así que vamos a ir a través de, y vamos a hacer [inaudible] y crear algunos marcadores. Así que ¿qué se escribe en el código? ESTUDIANTE: Me acaba de decir int límite uno es igual a 0. JASON HIRSCHHORN: Llamemos que int, comenzando. ESTUDIANTE: OK. JASON HIRSCHHORN: Eso hace más sentido para mí. ¿Y? ESTUDIANTE: Yo dije, supongo, int fin. JASON HIRSCHHORN: int fin. ESTUDIANTE: Supongo, n menos 1, o algo por el estilo. Al igual que, el último elemento. JASON HIRSCHHORN: Así que usted escribió, int comenzando igual a 0, y coma, y ​​int final es igual a n menos 1, punto y coma. Así que, esencialmente, lo que estamos haciendo aquí, 0 la primera posición. Y como sabemos, en arreglos, ellos no van hasta n, van hasta n menos 1. Así que tenemos algunos límites de nuestra matriz. Y estos límites iniciales resultan ser los límites iniciales de nuestro problema. Aceptar. Así que eso suena bien. Entonces, si nos remontamos a esta línea, mientras que Longitud de la lista es mayor que 0, lo que, en lugar de n, debe ponemos aquí? ESTUDIANTE: Escriba terminando minus principio. JASON HIRSCHHORN: Mientras que termina menos comienzo es mayor que 0? Aceptar. Y podríamos, si quisiéramos hacer que un poco más bonito, lo que otra cosa podíamos hacer? Si quisiéramos limpiar este código un poco? ¿Cómo podemos deshacernos del 0? Esta es sólo una cuestión de estilo. Es correcto en estos momentos. ESTUDIANTE: Ending no igualdad de principio? JASON HIRSCHHORN: Podemos hacer qué? [VOCES interponiendo] ESTUDIANTE: Ending es mayor? JASON HIRSCHHORN: Si. Sólo podemos hacer mientras que termina es mayor que principio. Derecha. Añadimos principio hasta el otro lado de eso, y nos libramos de la 0. Así que esto sólo se ve una poco más limpia. Aceptar. Así, mientras que la longitud de la lista es 0, escribimos que, si bien es mayor que termina que comenzar. Vamos a poner en nuestra necesaria llaves, y entonces lo primero que que queremos hacer es mirar a en una pequeña lista. Usted? ¿Me puede dar el - ESTUDIANTE: Si paréntesis valor corchete - JASON HIRSCHHORN: Si paréntesis corchete valor. ESTUDIANTE: Ending dividido por 2. JASON HIRSCHHORN: Ending? ESTUDIANTE: Yo veo un problema con su - JASON HIRSCHHORN: OK. Bueno, mira el centro. ¿Cómo sabemos lo que el medio es? Sí. Así que permítanme borrar ese código. ¿Cómo sabemos lo que el medio es? En cualquier cosa, cuando usted tiene el principio y al final, ¿cómo encontrar el medio? ESTUDIANTE: Promedias. ESTUDIANTE: Usted agregarlos juntos y luego - JASON HIRSCHHORN: Agréguelos juntos y luego? ESTUDIANTE: ¿Y usted hace un promedio. Divida por 2. JASON HIRSCHHORN: Agréguelos juntos y dividir por 2. Así int media es igual? Tom, usted puede dar a mí? ESTUDIANTE: A partir del plus de fin - JASON HIRSCHHORN: Inicio además de acabar. ESTUDIANTE: Todos, soporte, dividido por 2. JASON HIRSCHHORN: All, entre paréntesis, dividido por 2. Así que eso me da el medio de nada, ¿correcto? ESTUDIANTE: También es necesario redondear esto. JASON HIRSCHHORN: Lo que se hace significa, necesito redondear esto? [VOCES interponiendo] ESTUDIANTE: porque si es un extraño número, entonces es como - JASON HIRSCHHORN: Bueno, está bien. Así que podría redondear esto. Pero si es un número impar, a 5, lo que pueda teniendo 1 lejos de la mitad. O si es un número par, más bien, eso es un mejor caso. Si se trata de 4, solo tenemos 4, puedo tomar la primera "media", dijeron ellos o el segundo "medio". Cualquiera podría trabajar para una búsqueda binaria, así que en realidad no necesito redondear. Pero hay otra cosa que me que mirar a esta línea. Nosotros no podríamos darnos cuenta todavía, pero vamos a volver a ella. Debido a que esta línea en realidad todavía necesita una cosa más. Pero hasta ahora, hemos escrito cuatro líneas de código. Tenemos nuestro principio y terminando marcadores. Tenemos nuestro bucle while, que asigna de forma directa a nuestro pseudocódigo. Estamos pensando en el medio que se asigna directamente sobre nuestro pseudocódigo. Yo diría que esto va a la media de la lista, esta línea de código. Y luego, una vez que vamos a la mitad del la lista, lo siguiente que tenemos que hacer es comprobar si nuestro valor está ahí para el pseudocódigo que escribió antes. Entonces, ¿cómo comprobamos si nuestro valor está en la mitad de la lista? Usted. ¿Por qué no haces esto? ESTUDIANTE: Si nuestro valor es en el medio es igual a lo ponemos el - Quiero decir igual igual a - JASON HIRSCHHORN: It - Aceptar. ESTUDIANTE: No estoy seguro de lo que el variables que estamos buscando pues aunque, se debe a que - [VOCES interponiendo] ESTUDIANTE: [inaudible]. JASON HIRSCHHORN: Exactamente. Por la declaración de la función, estamos buscando a un valor. Así que estamos en busca de un valor en una matriz de valores. Así que estás en lo cierto. Que va a hacer, si el soporte de valor paren abierta centro cerrado iguales soporte igual valor, y en su interior ¿Qué necesitamos hacer? Si nuestro valor está ahí, lo que Qué tenemos que hacer? [VOCES interponiendo] ESTUDIANTE: Regreso cero. JASON HIRSCHHORN: Devuelve true. ESTUDIANTE: Devuelve true. JASON HIRSCHHORN: Michael, ¿qué hace esta línea? ESTUDIANTE: [inaudible] el programa se ha ejecutado su curso, y que ha terminado, y tienes lo que hay que hacer? JASON HIRSCHHORN: El programa o qué? En este caso? ESTUDIANTE: la función. JASON HIRSCHHORN: la función. Y así, para volver a lo que se llama y darle el valor, es cierto. Exactamente derecha. Principal. ¿Cuál es el tipo de retorno de principal, Michael? ESTUDIANTE: int, entero? JASON HIRSCHHORN: int, exactamente. Un entero. Eso fue sólo una pregunta para asegurarse ustedes han estado en la cima de la misma. ¿Qué se suele volver, si todas las cosas están funcionando bien? ESTUDIANTE: Zero. JASON HIRSCHHORN: Zero. Exactamente derecha. ESTUDIANTE: Si esto sólo devuelve true, no hay información que ofrecen sobre lo que el - Oh, esto es sólo decir que esa valor que está dentro de la matriz. JASON HIRSCHHORN: Exactamente. Este programa no está dando la información de dónde exactamente es el valor. Sólo está diciendo, sí, hemos encontrado ella, o no, nosotros no lo encontramos. Así que si se encuentra el número, devuelve true. Bueno, en realidad que acabamos de hacer que realmente rapidez con que una sola línea de código. Así que voy a pasar esa línea de pseudocódigo. ESTUDIANTE: ¿No necesitamos para cambiar la matriz? Debe ser valores, no de valor, ¿no? JASON HIRSCHHORN: Lo siento. Gracias. ESTUDIANTE: Sí. JASON HIRSCHHORN: Esta línea deben ser valores. Exactamente derecha. Aceptar. Así hemos visto la lista media. Si el número se encuentra return true. Continuando con nuestro pseudocódigo, si media es mayor, la búsqueda se fue. Así que tuve aquí, si el número de superior, la búsqueda se fue. Constantino, le puede dar me esta línea de código? ESTUDIANTE: Si el valor de la media - JASON HIRSCHHORN: Así que si el valor - si paren abierta valora soporte corchete de cierre media - ESTUDIANTE: ¿Es más pequeño que el valor? JASON HIRSCHHORN: ¿Es menor que. ESTUDIANTE: Inferior al valor. JASON HIRSCHHORN: Valor. Bueno, en realidad, desea comprobar si el número - Lo siento. Esto es un poco confuso. Pero lo demás, si el número de la medio de la lista es mayor. ESTUDIANTE: Oh, está bien. JASON HIRSCHHORN: voy a cambiar eso. Porque si en medio es más alto, desee buscar izquierdo, OK? Y ¿qué hacemos en el interior esto si condición? ESTUDIANTE: ¿Puedo hacer un pequeño cambio en la condición, el cambio a otra persona si? JASON HIRSCHHORN: Else if? Aceptar. Así que este código se ejecutará sobre el mismo. Pero lo bueno de usar if, else if, else if o if, else if, else significa que sólo uno de los que va a comprobar, no los tres de ellos, potencialmente. Y eso lo hace un poco mejor en el equipo que está funcionamiento de su programa. Así [? Constantino,?] estamos dentro de esta línea, de lo contrario, si los valores, corchete de cierre medio soporte es mayor que el valor. ¿Qué necesitamos hacer? Tenemos que buscar la izquierda. ¿Cómo hacemos eso? Voy a darle un nuevo comienzo. Tenemos estas dos cosas llamadas comenzando y terminando. Entonces, ¿qué tiene que suceder al principio? Si desea buscar en el lado izquierdo de la lista, conseguimos nuestro inicio de corriente. ¿Qué necesitamos para hacerlo? ESTUDIANTE: Fijamos el inicio a mitad más 1. JASON HIRSCHHORN: Entonces, si estamos la búsqueda de la izquierda? ESTUDIANTE: Lo sentimos, menos media - por lo que el final sería medio menos 1 e inicio - JASON HIRSCHHORN: ¿Y qué que sucede al principio? ESTUDIANTE: Se mantiene igual. JASON HIRSCHHORN: Así que el significado sigue siendo el mismo. Si estamos buscando la izquierda, estamos utilizando el mismo principio - exactamente correcto. Y el final? Lo sentimos, lo que hace el terminando igual otra vez? ESTUDIANTE: minus Medio 1. JASON HIRSCHHORN: minus Medio 1. Ahora, ¿por qué menos 1, no sólo del medio? ESTUDIANTE: El intermediario se queda fuera de la imaginarse ya, porque teníamos comprueba que está fuera? JASON HIRSCHHORN: Eso es exactamente correcto. El medio está fuera de la imagen. Ya hemos comprobado la media. Así que no queremos "el medio", cita Lo dijeron ellos, para seguir siendo en el matriz que estamos buscando. Así que esto es fantástico. Porque si media abrazadera valores es mayor de valor final iguales menos la mitad 1. Jeff, ¿qué pasa con esta última línea? ESTUDIANTE: Else. Valores medio es menor que el valor? JASON HIRSCHHORN: Vamos a que me estás dando más. Así que si no me das - ESTUDIANTE: Entonces comenzando sería más medio 1. JASON Hirschhorn: iguales Empezando más medio 1, de nuevo, para el mismo razón por la que Constantino nos dio antes. Y al final, que no ha dado me una línea de código todavía? Return false, Aleha, lo qué escribimos aquí? ESTUDIANTE: Regreso falsa. JASON HIRSCHHORN: Regresa falso. Y tenemos que hacerlo, porque si no lo encuentra, tenemos que decir que no lo encontré. Y dijimos que vamos a volver a bool, por lo que definitivamente tenemos que volver una en alguna parte bool. Así que vamos a ejecutar este código. De hecho voy a - así que estamos en el terminal. Limpiaremos nuestra ventana. Vamos a hacer todo. Encontramos que hay un error. Hay un error en la línea 15, que se espera punto y coma al final de la declaración. Entonces, ¿qué se me olvida? ESTUDIANTE: Punto y coma. JASON HIRSCHHORN: Punto y coma hasta aquí. Creo que fue el código de Tom. Así que Tom, [inaudible]. Es broma. Hagámoslo Marca Todas las de nuevo. ESTUDIANTE: ¿Qué directorio de Dropbox debemos estar en esto? JASON HIRSCHHORN: Así que usted puede simplemente ver para este bit. Pero, de nuevo, si se quería mover esta codificar en su directorio pset3 intentar a cabo, eso es lo que hice. Si te fijas aquí - lo siento, buena pregunta. [? LS,?] Tengo aquí el código find.c a partir del código distro de esta semana. Tengo helpers.h. Tengo un archivo Make que en realidad editado un poco para incluir estos nuevos archivos que estamos escribiendo. Todo ese código estarán disponibles, no el código de distribución, pero el nuevo Hacer de archivos, el nuevo archivo se helpers.h estará disponible en línea para su descarga. Una vez más, por lo que esos son los códigos extra que tienen. Así que hacen de todo, por esta línea, hace que encontrar, binario, la selección de la burbuja - marcas los tres de ellos y compila en este código hallazgo ejecutable. Así que en general, no queremos a directamente a check50. Queremos hacer algunas pruebas por nuestra cuenta. Pero sólo para que podamos agilizar esto un poco, check50 2013 pset3.find pasará en helpers.c-- mi mal. Yo no tengo eso en este momento. Así que estamos realmente va a ejecutar el código de verdad. Usage.find /, ya sabes lo que eso significa? ESTUDIANTE: Se necesita un segundo línea de comandos en ella. JASON HIRSCHHORN: Necesito una segunda línea de comandos. Y por la especificación, necesito para entrar en lo que estamos buscando. Así que vamos a ver el 42. Lo mantendremos en ordenada, porque no han escrito una función de clasificación con todo - 42, 43, 44. Y Control D No se encontró la la aguja en el pajar. Eso es malo. Es, sin duda existe. Vamos a intentar algo más. Tal vez sea porque me pongo que al principio. Vamos a hacer 41, 42, 43. Eso es. Se encontró. Vamos a ponerlo al final ahora, sólo para que podamos ser a fondo - 40, 41, 42. ¿No has encontrado la aguja. Así que he mencionado esto antes. Por desgracia, yo sabía que esto que iba a suceder. Sin embargo, para fines pedagógicos, es bueno para explorarlo. No trabaja. Por alguna razón, no lo puede encontrar. Sabemos lo que hay allí, pero no está resultando. Así que una cosa que podemos hacer es ir a través GDB para encontrarlo, pero no hace a nadie, sin pasar por el BGF, tienen una sentido de donde metimos la pata? [? Madu? ?] ESTUDIANTE: Yo creo que puede ser cuando se termina es igual al principio, y es sólo una lista de un solo elemento. Entonces, sólo hace caso omiso de que en lugar de hecho revisando. JASON HIRSCHHORN: Eso es exactamente correcto. Al final es igual principio, ¿verdad todavía tienen un elemento en nuestra lista? ESTUDIANTE: Sí. JASON HIRSCHHORN: Sí, de hecho, tener uno y sólo un elemento. Y que lo más probable ocurrir cuando, por el código que probamos, nos encontramos en el delante de un pajar o en el final de la pajar. Ahí es donde comienzo y final va a la igualdad de uno, con búsqueda binaria. Así que en estos dos casos no funcionó, porque termina fue igual al principio. Pero si termina es igual al principio, no ejecutar este bucle while? No lo hace. Y podríamos haber comprobado que de nuevo a través de BGF. Entonces, ¿cómo podemos solucionar este código, porque cuando, al poner fin es igual a empezando, también queremos esta while se ejecute. Entonces, ¿qué solución podemos hacer a la línea 18? ESTUDIANTE: [inaudible] es mayor que o igual a. JASON HIRSCHHORN: Exactamente. Mientras final es mayor que o igual al principio. Así que ahora, nos aseguramos de conseguir que caso esquina al final. Y vamos a ver. Vamos a ejecutar esto una vez más. Vamos a hacer todo. Una vez más, usted tiene que apenas siga por aquí. Encuentra 41 esta vez. Si prefieres algo más consistente. Encuentra 42. Vamos a ponerlo en el comienzo - 42, 43, 44. Lo encontramos. Así que fue realmente el cambio teníamos que hacer. Eso fue un montón de que la codificación acaba de hacer, la búsqueda binaria. ¿Alguien tiene alguna pregunta antes de Sigo adelante en las líneas que escribimos en búsqueda binaria o cómo nos imaginamos lo que hicimos averiguar? Antes de seguir adelante, también quiero señalar que por lo general, estudiamos nuestra pseudo-código de uno a uno en nuestro código. Tuvimos que cosa difícil averiguar con el comenzando y terminando. Pero había que no imaginé que fuera, usted habría escrito más o menos la Código idénticos, salvo por esas dos líneas superiores. Y entonces se habría dado cuenta cuando que lo hizo en los controles y los casos que necesita algo más. Así que incluso si se hubiera seguido nuestro línea de pseudo-código de línea, lo hubieras hecho conseguido, salvo en dos líneas de código que necesita para escribir. Y yo estaría dispuesto a apostar que ustedes todo habría averiguado bastante rápido, que necesitaba para poner algún tipo de marcador en allí para averiguar dónde estabas. Que de nuevo, es el poder de hacer pseudo-código antes de tiempo. Así que podemos hacer de la lógica, y luego podemos preocuparse por la sintaxis. Si lo hubiéramos confundido acerca de la lógica al intentar escribir el código en C, nos habría conseguido todo en mal estado. Y entonces estaríamos haciendo preguntas sobre la lógica y la sintaxis y mallado todos ellos juntos. Y nosotros habríamos entrado perdida en lo que puede convertirse rápidamente en un problema muy difícil. Así que vamos a pasar ahora a la selección de clasificación. Tenemos 20 minutos para el final. Así que tengo la sensación de que no vamos a ser capaces de conseguir a través de todos ordenación por selección y la ordenación de burbuja. Pero vamos a lo menos intento para terminar la selección de clasificación. Así implementar ordenación por selección utilizando el siguiente declaración de la función. De nuevo, esto se toma de la problema establece especificaciones. Valores int se corchetes, es una matriz de enteros. Y int.n es el tamaño de la matriz. Selección especie va para ordenar esta matriz. Así que por nuestro modelo mental de la selección Ordena, tiramos del - en primer lugar, vamos a través de la lista de la primera tiempo, encontrar el número más pequeño, ponerlo al principio, encontrar la segunda número más pequeño, lo puso en el segunda posición si queremos ordenar en orden ascendente. No estoy obligando a escribir pseudo-código en estos momentos. Pero antes de hacer el código como una clase en cinco minutos, vamos a escribir pseudo-código, así que tenemos un poco de sentido de donde vamos. Así que intentará escribir pseudo-código por su cuenta. Y luego tratar de convertir esa pseudo-código en el código. Haremos todo lo que como grupo en cinco minutos. Y, por supuesto, que me haga saber si tiene alguna pregunta. ESTUDIANTE: ¿Es todo? JASON HIRSCHHORN: Ver hasta dónde puede llegar en dos minutos más. Entiendo que no lo harás ser capaz de terminar. Pero vamos a ir sobre esto como un grupo. Todos están de codificación por lo que [inaudible], así que estoy lo siento para hacer una pausa lo que estás haciendo. Pero vamos a ir a través de este grupo. Y de nuevo, la búsqueda binaria, todos ustedes dan me uno si no más líneas de código. Gracias por eso. Vamos a hacer lo mismo aquí, código juntos como un grupo. Así ordenación por selección - vamos a escribir algunos pseudo-código rápido. Según el modelo mental, alguien puede darme la primera línea de pseudo-código, por favor? ¿Qué quiero hacer? ESTUDIANTE: Si bien la lista está fuera de orden. JASON HIRSCHHORN: OK, mientras que la lista está fuera de servicio. Y ¿qué quiere decir "fuera de servicio?" ESTUDIANTE: Mientras [inaudible] no se ha solucionado. JASON HIRSCHHORN: Si bien la lista está fuera de servicio, ¿qué hacemos? Dame la segunda línea, por favor, Marcus. ESTUDIANTE: Entonces encontrar la siguiente número más pequeño. Esta será una sangría. JASON HIRSCHHORN: Así que encontrar la siguiente número más pequeño. Y entonces alguien más? Una vez que encontramos la inmediata inferior número, ¿qué hacemos? Voy a decir encontrar el número más pequeño. Eso es lo que queremos hacer. Así que encontrar el número más pequeño. Entonces, ¿qué hacemos? ESTUDIANTE: [inaudible] a principio. JASON HIRSCHHORN: ¿Lo sientes? ESTUDIANTE: Colóquelo en el principio de la lista. JASON HIRSCHHORN: Así que lo coloca en el principio de la lista. Y lo hacemos a lo que era en el principio de la lista, ¿no? Estamos sobrescribir algo. Entonces, ¿dónde ponemos eso? Sí, Anna? ESTUDIANTE: ¿Dónde los más pequeños número era? JASON Hirshhorn: Así que ponga el inicio de la lista donde la número más pequeño era. Así, mientras que la lista está fuera de orden, encontrar el número más pequeño, colóquelo en el principio de la lista, poner el principio de la lista, donde el número más pequeño era. Marcus, puede reformular esta línea mientras que la lista está fuera de servicio? ESTUDIANTE: Si bien las cifras no han sido ordenados? JASON Hirshhorn: OK, por lo que con el fin de saben que los números no han sido ordenados, ¿qué tenemos que hacer? ¿Cuánto tenemos que ir a través de esta lista? ESTUDIANTE: Así que supongo que un bucle for, o mientras que, mientras que los números revisados ​​es menos que la longitud de la lista? JASON Hirshhorn: OK, eso es bueno. Creo que misphrased mi pregunta mal. Yo sólo estaba tratando de llegar a vamos a tener que ir a través de toda la lista. Así, mientras que la lista está fuera de servicio, para mí, es difícil asignar sucesivamente. Pero, básicamente, eso es lo Pienso en esto. Ir a través de toda la lista, busque el número más pequeño, colóquelo en el comenzando - en realidad, tienes razón. Vamos a poner a los dos. Así, mientras que la lista está fuera de orden, que pasar por toda la lista una vez, encontrar el menor número, el lugar en el principio de la lista, poner el principio de la lista, donde el número más pequeño era, y entonces, si la lista es aún fuera de orden, no tenemos tiene que ir a través de este proceso de nuevo, ¿verdad? Es por eso que la selección de género, tiempo de ejecución de Big-O de ordenación por selección, cualquier persona? ESTUDIANTE: n al cuadrado. JASON Hirshhorn: n al cuadrado. Porque al igual que Marcus y yo acabo de dar cuenta aquí, vamos a tener que pasar por la lista de la lista número de veces. Así que pasando por algo de longitud n n número de veces es, de hecho, n al cuadrado. Así que este es nuestro pseudocódigo. Esto se ve muy bien. ¿Alguien tiene alguna pregunta sobre el pseudocódigo? Porque en realidad ordenación por selección debe Probablemente venga uno a uno, el código de pseudocódigo. Así que cualquier pregunta acerca de la lógica del pseudocódigo? Por favor, pregunte ahora. Selección clase - mientras que la lista está fuera de orden, vamos a ir a través de él y encontrar el más pequeño cada vez y lo puso en la parte delantera. Así, mientras que la lista está fuera de servicio, puede alguien me dé esa línea de código que No me ha dado una línea de código, sin embargo, por favor? Suena como un qué? ESTUDIANTE: Es un bucle for. JASON Hirshhorn: Suena Quieres un bucle for. Bien, ¿me puede dar el bucle? For - ESTUDIANTE: i es igual a 0. JASON Hirshhorn: io - lo que nos estamos perdiendo? ¿Qué pasa aquí? ESTUDIANTE: Int. JASON Hirshhorn: Exactamente. (Int i = 0; - ESTUDIANTE: i