[MÚSICA]
[MÚSICA]
Bienvenidos nuevamente.
En las sesiones pasadas hemos trabajado sobre cómo definir arreglos,
ya sea de tamaño fijo o de tamaño variable,
y cómo hace recorridos sobre ellos.
En esta sesión trabajaremos sobre cómo hacer búsqueda sobre los elementos
que se encuentran en el arreglo.
Iniciaremos con las búsquedas secuenciales,
lo primero que debemos pensar es que para realizar una búsqueda
debemos iniciar por definir
la característica, o características, que nos permitirán hacer la búsqueda.
Luego
debemos revisar cada uno de los elementos del arreglo
y preguntar si el elemento cumple con las características que hemos establecido.
Es decir, debemos hacer un recorrido por los elementos del arreglo.
Finalmente, una vez encontremos el elemento que estamos buscando, debemos detenernos,
puede que tengamos que revisar todos los elementos del arreglo o no,
dependiendo de cuál sea la característica que decidimos
para realizar nuestra búsqueda.
Veamos algunos ejemplos,
pensemos en nuestro ejemplo de la pizzería,
nos podrían preguntar, por ejemplo, si un cocinero prepara la pizza
cuyo nombre llega por parámetro,
o nos podrían preguntar, ¿cuál es la pizza más barata que sabe preparar un cocinero?
Ambos son búsquedas, sin embargo las resolveremos de manera diferente.
Empecemos por el primer caso,
en el si queremos saber si un cocinero prepara una pizza
cuyo nombre llega por parámetro.
Para esto
veamos el siguiente diagrama y pensemos qué es lo que tenemos que hacer,
lo primero es definir el criterio de búsqueda,
en este caso es sencillo, el criterio de búsqueda es el nombre.
Una vez identificado esto, debemos empezar a revisar los elementos,
lo más sencillo es iniciar por el primer elemento del arreglo,
a este le preguntaremos si su nombre es el nombre que nos están preguntando,
de ser así, hemos terminado y hemos encontrado
que el cocinero sí prepara la pizza.
De lo contrario, debemos avanzar a la siguiente pizza,
a la pizza de la posición uno le preguntaremos su nombre
y miraremos si es el nombre
que nos están preguntando,
de ser así hemos terminado, de lo contrario, avanzaremos a la siguiente pizza.
Con la pizza dos repetiremos el proceso,
supongamos que ella no es la pizza buscada, entonces avanzaremos a la pizza tres.
Supongamos ella es la pizza buscada,
es decir, hemos encontrado que el cocinero sí prepara la pizza que nos están preguntando,
por lo tanto, podemos terminar el recorrido.
Veamos ahora cuáles son los pasos para poder implementar este algoritmo,
lo más sencillo es iniciar
asumiendo el peor caso,
es decir,
suponiendo que el cocinero no prepara la pizza por la cual nos están preguntando.
Luego pasaremos a revisar le primera pizza,
y puede ocurrir uno de los siguientes casos:
el primero que la pizza sea la que estamos buscando,
en este caso
nos detendremos y diremos que el cocinero sí prepara la pizza.
El segundo caso que puede ocurrir es que
la primera pizza no sea la pizza que estamos buscando,
en ese caso entonces avanzaremos a la siguiente pizza y repetiremos el proceso,
y seguiremos haciendo lo mismo hasta que encontremos la pizza buscada,
o hasta que se acaben las pizzas del arreglo de pizzas del cocinero.
Ahora tomemos estos pasos del algoritmo y tratemos de convertirlos en códigos,
para eso traigamos la declaración de la clase pizza
y construyamos el método preparar Pizza,
el cual nos indica si un cocinero prepara o no la pizza cuyo nombre llega por parámetro.
El primer paso decía que asumiéramos el peor caso,
por lo tanto, lo que haremos es crear una variable
que diga que el cocinero no prepara la pizza,
es decir, una variable booleana que inicia en false.
Y sabemos que al final del método debemos devolver
el valor que queda almacenado en esta variable.
El segundo paso decía que recuperáramos la primera pizza,
para esto usaremos la instrucción get de ArrayList,
y le pediremos que nos entregue la pizza de la posición cero.
El tercer paso nos dice que regresemos si la pizza es la que estamos buscando.
Para esto con una instrucción condicional podemos preguntar
si el nombre de la pizza actual es igual al nombre del que nos llega por parámetro,
en caso de que sea verdadero
diremos que el cocinero sí prepara la pizza.
El cuarto paso decía que si no era la pizza buscada,
debíamos avanzar a la siguiente y repetir el proceso,
es decir, debemos construir una instrucción repetitiva,
y adicionalmente nos indicaba que si encontrábamos la pizza buscada
nos detuviéramos.
Es decir, que tendremos un recorrido parcial.
Ya sabemos que para hacer un recorrido podemos usar las instrucciones for await,
en este caso usemos la instrucción for.
El recorrido iniciará
en la pizza de la posición cero, terminará cuando se acaben las pizzas,
o cuando encontremos que el cocinero sí prepara la pizza,
y avanzará una a una por las pizzas.
Veamos que en este caso siempre estamos recuperando la pizza de la posición cero,
esto no es correcto. Debemos recuperar la pizza que estemos revisando en ese momento,
para esto cambiaremos esta instrucción get,
por una instrucción get que recupere la pizza de la posición "i",
con este método ya podemos responder
a la búsqueda de si un cocinero prepara o no una pizza cuyo nombre llega por parámetro.
Pasemos a la siguiente búsqueda,
en la cual nos piden identificar
cuál es la pizza más barata que sabe preparar un cocinero.
Para eso tratemos de identificar los pasos que debemos seguir,
nuevamente lo más fácil es iniciar suponiendo el peor caso,
es decir,
suponer que el cocinero no prepara ninguna pizza.
En caso de que el cocinero si prepare pizzas,
lo más sencillo es asumir que la primera es la más barata,
luego empezaremos a revisar las demás pizzas,
al revisar la segunda pizza, la compararemos con la primera,
si la segunda es más barata que la primera
quiere decir que hasta este momento la segunda es la más barata.
Luego pasaremos a la tercera
y repetiremos el mismo proceso,
y así sucesivamente hasta que acabemos con todas las pizzas,
en general
lo que tenemos que hacer es revisar si la pizza que estamos revisando actualmente
tiene un precio menor a la pizza que tenemos almacenada como la más barata,
si es así, debemos actualizar la más barata
a la que estamos revisando en este momento.
Veámoslo en un diagrama,
supongamos que tenemos este arreglo de pizzas
y vamos a buscar la más barata.
A simple vista, sabemos que es la de 14.000,
sin embargo, veamos cuál es el algoritmo que debemos indicarle
a nuestro programa para que logre hacer esa tarea.
Iniciemos asumiendo el peor caso,
es decir, que la más barata es ninguna,
o sea, que le cocinero no prepara ninguna pizza,
luego
como el cocinero sí prepara pizzas, asumamos que la más barata es la primera.
Y pasemos a revisar la segunda pizza,
comparemos los precios entre la segunda y la más barata,
como la segunda no es más barata
que la que hasta el momento tenemos registrada como la más barata,
no haremos ningún cambio y pasaremos a la siguiente pizza,
la pizza de $17.000,
en este caso
la pizza de 17.000 es más barata que la pizza de 18.000,
por tanto debemos actualizar la más barata
a la de 17.000,
y pasemos
a la siguiente pizza.
En este caso 21.000 no es menor a 17.000, por lo tanto, no debemos hacer ningún cambio.
Ahora pasemos a la siguiente pizza,
la pizza de 14.000 sí es menor que la pizza de 17.000,
por lo tanto, lo que debemos hacer es actualizar la pizza
más barata a la pizza de 14.000,
y pasamos a la siguiente pizza,
para este caso 18.500 no es menor que 14.000,
por tanto, no debemos actualizar la más barata,
y hemos encontrado que la más barata es la de 14.000.
Es importante ver que en este caso debimos revisar todas las pizzas,
ya que es posible que la más barata
se encuentre en la última posición del arreglo.
Veamos cómo logramos convertir este algoritmo a código,
para eso traigamos la declaración de la clase pizza y construyamos el método
darPizzaMasBarata.
Iniciaremos asumiendo el peor caso,
es decir, que el cocinero no prepara ninguna pizza,
para esto crearemos una variable
llamada menor, la cual iniciaremos en null.
Ahora sabemos que tenemos que hacer un recorrido por todas las pizzas,
dado que es por todas las pizzas,
traeremos la estructura de un recorrido total,
ahora recuperaremos la pizza de la posición que estamos revisando actualmente,
es decir, haremos get de la posición "i",
y empezaremos a evaluar los posibles casos,
el primero es que aún no hayamos encontrado a ninguna pizza
que sea la más barata,
este caso solo ocurrirá
para la pizza de la posición cero.
Si ocurre esto, entonces diremos que la más barata
es la pizza que estamos revisando en este momento,
en caso de que ya tengamos una pizza registrada como la más barata,
lo que debemos hacer es comparar las dos pizzas,
las más barata y la que estamos revisando en este momento,
en caso de que la que estamos revisando en este momento
tenga un precio menor a la más barata,
actualizaremos la más barata
y diremos que ahora es la que estamos revisando en este momento.
Es importante resaltar que si, por ejemplo, quisiéramos buscar la pizza más cara,
lo único que debemos hacer es invertir el símbolo
que estamos usando para comparar los precios de las pizzas.
Veamos ahora otras posibles búsquedas que nos podrían plantear,
pero primero hagamos ciertas suposiciones,
por ejemplo,
supongamos que las pizzas estuvieran ordenadas por precio,
en este caso si nos preguntaran cuál es la pizza más barata, ¿qué podríamos hacer?
Pues simplemente podríamos devolver la primera pizza,
o supongamos que las pizzas se encuentran ordenadas por nombre,
¿será que existe alguna manera de buscar
si el cocinero prepara o no una pizza dado su nombre
de manera más fácil? Es decir, que revisemos menos elementos.
Sí es posible,
y ese ese segundo tipo de búsquedas que vamos a realizar en esta sesión,
estas son las búsquedas binarias,
lo primero que tenemos que tener en cuenta para la búsquedas binarias
es que solo funcionan
siempre y cuando los elementos se encuentren ordenados
por el criterio de búsqueda que hemos seleccionado.
Sabiendo esto,
la búsqueda binaria funcionará de la siguiente manera:
siempre tomará el elemento de la mitad del arreglo.
En caso de que el elemento de la mitad sea el buscado, perfecto, hemos terminado;
de lo contrario, si no es el buscado, lo que haremos es descartar alguna de las mitades,
ya sea la mitad inferior o la mitad superior,
dependiendo de si el elemento buscado
es más grande o más pequeño que el elemento de la mitad.
Y luego repetiremos este proceso hasta que no haya más elementos, o
hasta que hayamos encontrado el elemento buscado.
Veámoslo en un diagrama,
supongamos que tenemos este arreglo de pizzas,
y nos piden identificar
si el cocinero prepara la pizza cuyo nombre es pepperoni,
es importante notar
que en este caso las pizzas se encuentran ordenadas alfabéticamente
de manera ascendente.
Siguiendo un algoritmo de búsqueda binaria,
lo que haremos será establecer cuál es la pizza de la mitad;
para esto debemos identificar cuál es el inicio y cuál es el fin del arreglo,
y a partir de ellos podemos calcular el medio.
En el medio está la pizza italiana, la cual no es la pizza de pepperoni,
sin embargo,
al hacer este análisis podemos descartar toda la mitad inferior,
ya que sabemos que pepperoni tiene que ser mayor
que italiana, alfabéticamente.
Ahora actualizaremos el inicio dado que descartamos la mitad inferior.
Al actualizar en el inicio también actualizaremos el medio.
Y ahora iremos a evaluar el nuevo elemento del medio,
en este caso rancho,
como rancho no es pepperoni,
no hemos encontrado el elemento,
sin embargo, podemos descartar la mitad superior,
ya que sabemos que pepperoni es menor alfabéticamente que rancho.
Como descartamos la mitad superior,
actualizaremos el fin,
y nuevamente volvemos a calcular el medio,
en este caso el medio es pepperoni,
por lo tanto, hemos llegado a la pizza que estamos buscando.
Veamos un segundo caso,
el caso en que nos preguntan si el cocinero prepara la pizza americana.
A simple vista sabemos que no lo hace,
sin embargo, veamos cómo funcionaría el algoritmo en este caso.
Nuevamente definiremos el inicio y el fin
e identificaremos el elemento de la mitad,
nuevamente es italiana.
Compararemos italiana con americana, dado que no son iguales
no hemos encontrado el elemento.
Sin embargo, ya podemos descartar toda la mitad superior
dado que sabemos que americana es menor que italiana alfabéticamente.
Como descartamos la mitad superior, actualizaremos el fin,
y nuevamente calcularemos el medio;
ahora el medio es carnes,
como no es igual que americana,
no hemos encontrado el elemento, sin embargo, ya podemos descartar
toda la mitad superior,
dado que sabemos que americana es menor alfabéticamente que carnes.
Y nuevamente actualizaremos inicio, fin y medio.
En este caso, como nos hemos salido de los límites del arreglo,
podemos decir que no hemos encontrado
a la pizza americana y terminamos nuestra búsqueda.
Veamos cómo podemos convertir esta búsqueda binaria a código,
para eso construyamos el método preparaPizza.
Como hicimos la vez pasada, crearemos una variable de tipo booleano
que inicia asumiendo el peor caso, y al final devolveremos esta variable.
Lo primero que debemos hacer para poder hacer la búsqueda binaria
es definir el inicio y el fin del arreglo,
en este caso el inicio será la pizza de la posición cero,
y el final será la pizza de la última posición.
Lo siguiente que debemos hacer es calcular la mitad;
la mitad simplemente será el promedio entre el inicio y el fin.
Lo siguiente es empezar a evaluar las pizzas,
para esto pues haremos un recorrido que nos permita ir recorriendo
cada uno de los elementos que se encuentra en la mitad.
Sabemos que nos debemos detener cuando hayamos encontrado el cocinero
prepara la pizza buscada o cuando nos salgamos de los límites del arreglo;
sabiendo esto, recuperaremos la pizza del centro
y empezaremos a evaluar los posibles casos,
el primero es que la pizza
sea la pizza que estamos buscando.
En este caso para realizar la comparación
entre el elemento central y el nombre que llega por parámetro,
hemos usado el método compareTo de la clase String.
Este método nos permite identificar
si una cadena es menor, mayor o igual a otra.
Sabiendo esto
podemos ir a construir el primer caso en el que las dos cadenas son iguales,
si es así, quiere decir que el cocinero sí prepara la pizza.
El siguiente caso
es el que la pizza del medio tiene un valor mayor
a la pizza cuyo nombre llega por parámetro,
en este caso descartamos toda la mitad superior,
por lo que actualizamos el final
y lo hacemos que ahora valga la mitad menos uno.
En caso contrario, en caso de que la pizza del centro tenga un valor
menor al que llega por parámetro,
descartamos la otra mitad y actualizamos el inicio
diciendo que el inicio es igual a medio más uno.
Ahora bien, se supone que en cada iteración de nuestro recorrido
deberíamos actualizar el medio.
Entonces, el cálculo del medio lo haremos dentro del recorrido.
Con esto hemos logrado construir una búsqueda binaria,
la cual no necesita recorrer todos los elementos sino que recorre
de a mitades para poder identificar o buscar
un elemento que nos están consultando.
Con esto hemos terminado el tema de búsquedas;
en la siguiente sesión revisaremos un caso de estudio
donde aplicaremos todos los temas vistos.
[MÚSICA]
