[MÚSICA] [MÚSICA] Hola y bienvenidos a la lección de búsquedas. En esta ocasión, vamos a ver otros tipos de búsquedas fundamentales. Como bien sabemos, el problema de manejar grandes cantidades de datos en nuestro paradigma no se limita solamente a organizarlos, sino también a realizar búsquedas eficientes sobre los mismos. En lecciones anteriores hemos visto los patrones de búsqueda básica sobre arreglos en una y dos dimensiones. Esta vez vamos a hablar de casos particulares de búsquedas, y por facilidad, lo haremos sobre arreglos en una dimensión. Esto obviamente se puede generalizar para matrices y arreglos de dimensiones superiores. Para ilustrar, usaremos un director telefónico. Empecemos por el primer caso, búsqueda del elemento mayor o del elemento menor. Tomaremos una página del directorio y miremos a las personas cuyo apellido es Díaz. Vamos a buscar a la persona de apellido Díaz en esta página cuyo nombre sea el más largo. Empecemos por el primero, Jorge. Como hasta ahora solo hemos revisado un elemento, es obvio que Jorge es el nombre más largo. Luego vamos a memorizar a Jorge. Comparamos con Jadey, el siguiente nombre. Jadey es más corto que Jorge, luego continuamos con Jorge en nuestra memoria. La siguiente es Beatriz, Beatriz es más larga que Jorge. Luego olvidamos a Jorge y memorizamos a Beatriz. La siguiente es Ana, Ana es más corta. Luego continuamos con Beatriz, y llegamos a Adriana. Y nos damos cuenta que Beatriz es de la misma longitud que Adriana. Entonces, podemos proceder de dos maneras. Podemos asumir que el primer nombre más largo que encontramos siempre es más importante y que solo lo reemplazaremos si hay alguno estrictamente mayor, o podemos asumir que el último que encontremos tiene prioridad. Y en este caso lo reemplazamos. Para esta ocasión, vamos a continuar con Beatriz. El siguiente es María, es más corto. Luego Vilma, más corto, Beatriz sigue en nuestra memoria. Luis, Juan, Óscar, tenemos a dos Miriams, y todos estos son más cortos, luego no hay necesidad de quitar de nuestra memoria, de olvidar a Beatriz. Luego Mario, y finalmente Julia. Con estos dos hemos llegado al final de nuestra búsqueda, y Beatriz es el nombre más largo presente en esta página. Notemos algunas cosas importantes. Esta búsqueda es un caso particular de recorrido total, estamos obligados a recorrer siempre todo el arreglo en búsqueda de un elemento de mayor o menor valor. Y siempre comparamos el elemento que miramos en el recorrido del arreglo con el que memorizamos, y no con los otros. Al ser un recorrido total, la eficiencia de este algoritmo será de O(n) y de Omega(n). En cualquier caso, siempre tendremos que recorrer todos los elementos del arreglo. Ahora veamos el pseudocódigo para este tipo particular de búsqueda. Veamos, pues, a través del pseudocódigo una situación equivalente. Esta vez vamos a buscar el elemento menor de nuestro arreglo. Así que comencemos, sea A nuestro arreglo. Y vamos a asumir inicialmente que el primer elemento del arreglo va a ser el elemento menor. Como no conocemos los demás elementos, esta suposición nos va a permitir empezar para luego hacer las comparaciones que vienen al caso. Y sea N igual a uno. Como en los anteriores ejemplos, N va a permitir desplazarnos por cada una de las posiciones del arreglo. No va a comenzar en cero porque ya sabemos que nuestro primer elemento con el que vamos a empezar a comparar lo tenemos en elemento menor. Así que comenzamos por la posición inmediatamente siguiente, es decir, uno. Y vamos a iterar, como es normal en estas situaciones, hasta que N iguale el tamaño del arreglo. Y vamos a tener un condicional bastante simple. Si el elemento menor, es decir, el que tenemos guardado en la variable, sea al principio o sea en cualquier momento de la iteración obviamente, es mayor al elemento de la posición N de nuestro arreglo A. Y cuando decimos, "Es mayor", hablamos de la comparación que queramos hacer si son cadenas de caracteres por tamaño. O sin son números, por valor, o sin son objetos, será de acuerdo como nosotros hayamos definido cómo comparar un objeto contra otro. También podríamos expresar este condicional como si el elemento en la posición N es menor que el elemento menor hasta el momento, si se cumple eso, entonces simplemente reemplazamos el valor del elemento menor por el valor del elemento en la posición N en el arreglo A. Evidentemente, al final de nuestra iteración tenemos que incrementar el valor de N en una unidad para poder progresar en el ciclo. Y finalmente, una vez terminamos de iterar, retornamos el elemento menor. Este es un caso de recorrido total, porque para estar seguro que hemos encontrado el elemento menor de nuestro arreglo, es necesario recorrer todas y cada una de las posiciones del mismo. Ahora veamos otro tipo de búsqueda particular, la búsqueda binaria. Y vamos a usar esta vez un volumen mayor de datos, usemos un directorio más grande. Empecemos pensando que vamos a buscar a alguien particular en el directorio, a Andrea Gutiérrez. Si abordáramos este problema de la manera tradicional, tendríamos que empezar desde la primera página del directorio y realizar una búsqueda en recorrido parcial, revisando página por página por página hasta que encontremos a Andrea Gutiérrez. [MÚSICA] Y hemos llegado, Andrea Gutiérrez. Ya vemos el problema, cuando tenemos una enorme cantidad de datos nos vamos a demorar una enorme cantidad de tiempo. Y vamos a tener una complejidad de O(n) y de Omega(n). En el peor de los casos estaremos buscando a Zaida Zambrano, y en el mejor a Abelardo Aarón. ¿Cómo podemos mejorar esto? Aquí entra el algoritmo de búsqueda binaria. En lugar de comenzar por el principio, vamos a comenzar por la mitad. Llegamos a la M de Molina, entonces vamos a marcar aquí. Ya hemos revisado la mitad, y vamos a descartar la segunda mitad porque sabemos que Andrea Gutiérrez no se va a encontrar acá. Vamos a mirar entonces y a dividir esta porción que queda por la mitad, nuevamente. Y hemos aterrizado en la C, en Cortez. En este caso, sabemos que en esta porción no se va a encontrar Andrea Gutiérrez. Así que vamos a revisar esta porción de arreglo. Vamos a dividirlo también por la mitad, aproximadamente. Y vamos a aterrizar en la F, en Forigua. En este caso, sabemos que Andrea tampoco está en la primera mitad, entre este y este, sino que está en esta mitad. Así que vamos a dividir esta porción de arreglo que nos queda, nuevamente por la mitad. Y hemos llegado a Andrea Gutiérrez, todo utilizando la búsqueda binaria. Nos hemos demorado mucho menos tiempo. De hecho, las complejidades del algoritmo serán más cortas. En el peor de los casos tendremos que revisitar alrededor del logaritmo base dos de n elementos, es decir, la complejidad de o de logaritmo base dos de N. ¿Por qué? Bueno, usemos un poco de matemáticas. Cada vez que dividimos nuestro arreglo, lo hacemos en dos. La primera vez tendremos n medios elementos. La segunda vez dividiremos la mitad en dos, y tendremos n cuarto elementos. La tercera vez será la mitad de la mitad de la mitad, n octavo elementos. Y así sucesivamente, ¿vemos el patrón? Claro. Nuestro arreglo dividido tendrá n sobre dos a la i, donde i es el número de veces que hemos dividido el directorio. ¿Hasta cuándo podemos seguir dividiendo el directorio? Simple, hasta que nos quede solo un elemento. Es decir, cuando n sobre dos a la i sea igual a uno. Si resolvemos la ecuación para i, entonces podemos hacer logaritmo base dos de n divisiones, de ahí la complejidad en el peor de los casos. Es decir, en el caso en el que no encontremos el elemento y tengamos que dividir hasta que no sea posible dividir más, va a darnos logaritmo base dos de n. En el mejor caso, el elemento está justo en medio, así que omega uno. Mirando ambas funciones, podemos concluir que la búsqueda binaria siempre será mejor que la búsqueda secuencial para grandes volúmenes de datos. Pero, hey, hay una trampa. ¿Notaron que característica especial tenía nuestro arreglo? En efecto, estaba ordenado alfabeticamente. Si el arreglo sobre el que buscamos no está ordenado usando la característica sobre la que haremos la búsqueda, el algoritmo no funciona. Y es ahí donde debemos decidir si es mejor implementar búsqueda secuencial u ordenar previamente los elementos para aplicar la búsqueda binaria. Vamos a ver, ahora que sabemos esto, el pseudocódigo para la búsqueda binaria. Esta vez el algoritmo parece un poco más complicado, pero no es nada que no podamos desglosar y entender parte, parte. Como siempre, A será nuestro arreglo de elementos. Y vamos a declarar dos variables, inicio y fin, que van a representar el comienzo y el final del arreglo en el que estemos iterando. Inicialmente va a ser del arreglo A, pero posteriormente va a ser de los subarreglos que vamos a formar al dividirlo por la mitad y por la mitad de la mitad y por la mitad de la mitad y así sucesivamente. Así que inicializamos inicio en cero, la primera posición del arreglo A. Y fin en tamaño del arreglo -1, es decir, la última posición. Adicionalmente, incluimos las variables, posición elemento buscado y encontrado. La posición elemento buscado representa la posición del elemento que estamos buscando dentro del arreglo, y por convención será igual a -1 si no está dentro del arreglo, que es una posibilidad. Y encontrado, una variable booleana que indica si hemos o no ya encontrado el elemento. Y comienza en falso. Entonces vamos a iterar mientras que encontrado sea igual a falso, es decir, no hayamos encontrado el elemento, e inicio sea menor o igual a fin. Esto puede parecer poco intuitivo, pero mirémoslo así. La idea del algoritmo es que tomemos nuestro arreglo, nos paremos en la mitad y miremos si ese elemento corresponde al que buscamos. Si el que buscamos es menor, vamos a tomar la primera mitad, y si es mayor vamos a tomar la segunda mitad. Y lo que vamos a hacer es actualizar las variables inicio y fin para saber sobre qué subarreglos vamos a ir iterando. No obstante, cuando lleguemos a un punto en el que inicio sea mayor que fin, es decir, que las posiciones se inviertan, sabremos que no podemos buscar más sobre el arreglo y que el elemento no está presente. Entonces veamos, el medio va a ser nuestra variable y que va a ser igual justamente a la mitad del arreglo, es decir, inicio más fin sobre dos. Si el elemento en la posición medio del arreglo es igual al elemento buscado, entonces decimos, "Bueno, la posición del elemento buscado es igual a medio, porque lo acabamos de encontrar acá, y encontrado igual a verdadero". Para que el ciclo se termine una vez vaya a comenzar la siguiente iteración. Por el contrario, si el elemento en la posición medio del arreglo A resulta ser menor que el elemento buscado, entonces vamos a buscarlo en la mitad de los elementos que son mayores. Es decir, inicio va a ser igual a medio más uno. Vamos a buscar en el subarreglo desde la mitad hasta el final. Por el contrario, si el elemento en la posición medio resulta ser mayor que elemento buscado, en ese caso vamos a buscarlo en el subarreglo de elementos menores. Es decir, vamos a tomar desde el principio original hasta la mitad. O lo que es lo mismo, actualizamos la variable fin para que sea igual a medio menos uno, es decir, el elemento que está antes de la mitad. Y como podemos ver en las siguientes iteraciones, vamos a seguir realizando estas búsquedas reduciendo cada vez más el arreglo a la mitad, luego a la mitad de la mitad. Luego a la mitad de la mitad de la mitad, como vimos en el directorio, hasta que lo encontremos o hasta que nos demos cuenta que el elemento no está presente. Finalmente, retornamos posición elemento buscado al final de nuestro método, que será -1 si no está presente, como lo hemos dicho, o la posición en la que estaba ubicado. En cualquier caso, lo último que hacemos es retornar la posición del elemento buscado. Bien, esperamos que hayan quedado claras las búsquedas de elementos de mayor o menor valor y las búsquedas binarias. Los invitamos a aplicar estos nuevos conocimientos en los ejercicios. [MÚSICA]
