busqueda binaria y ventanas deslizantes - … · dado un arreglo ordenado de n numeros (a),...
TRANSCRIPT
![Page 1: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/1.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Busqueda Binaria y Ventanas DeslizantesCertamen Nacional de OIA
Facundo Gutierrez
Octubre 2017
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 2: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/2.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Esquema General
1 Busqueda BinariaEjemplo Motivador
Solucion con Busqueda LinealSolucion con Busqueda Binaria
Propiedades BinariasEjemplos
Evolucionando PokemonesMaximo Cuadrado en unTableroCamino que minimiza lamaxima arista
Problemas de Tarea
2 Intervalo3 Ventanas Deslizantes
Ejemplo MotivadorIdeas y ConceptosEjemplos
2SUMK-esima distancia entre puntosde la recta
Problemas de Tarea
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 3: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/3.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Buscar un elemento en un arreglo ordenado
Problema:
Dado un arreglo ordenado de n numeros (A), queremos saber si elelemento x se encuentra en el. En caso de encontrarse, buscamosla posicion exacta de su primera aparicion.
Ejemplos:
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 6
La respuesta es : ”El elemento x = 6 se encuentra en elarreglo A por primera vez en la posicion 2”
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 7
La respuesta es : ”El elemento x = 7 no se encuentra en elarreglo A”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 4: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/4.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Buscar un elemento en un arreglo ordenado
Problema:
Dado un arreglo ordenado de n numeros (A), queremos saber si elelemento x se encuentra en el. En caso de encontrarse, buscamosla posicion exacta de su primera aparicion.
Ejemplos:
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 6
La respuesta es : ”El elemento x = 6 se encuentra en elarreglo A por primera vez en la posicion 2”
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 7
La respuesta es : ”El elemento x = 7 no se encuentra en elarreglo A”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 5: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/5.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Buscar un elemento en un arreglo ordenado
Problema:
Dado un arreglo ordenado de n numeros (A), queremos saber si elelemento x se encuentra en el. En caso de encontrarse, buscamosla posicion exacta de su primera aparicion.
Ejemplos:
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 6
La respuesta es : ”El elemento x = 6 se encuentra en elarreglo A por primera vez en la posicion 2”
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 7
La respuesta es : ”El elemento x = 7 no se encuentra en elarreglo A”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 6: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/6.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Buscar un elemento en un arreglo ordenado
Problema:
Dado un arreglo ordenado de n numeros (A), queremos saber si elelemento x se encuentra en el. En caso de encontrarse, buscamosla posicion exacta de su primera aparicion.
Ejemplos:
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 6
La respuesta es :
”El elemento x = 6 se encuentra en elarreglo A por primera vez en la posicion 2”
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 7
La respuesta es : ”El elemento x = 7 no se encuentra en elarreglo A”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 7: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/7.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Buscar un elemento en un arreglo ordenado
Problema:
Dado un arreglo ordenado de n numeros (A), queremos saber si elelemento x se encuentra en el. En caso de encontrarse, buscamosla posicion exacta de su primera aparicion.
Ejemplos:
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 6
La respuesta es : ”El elemento x = 6 se encuentra en elarreglo A por primera vez en la posicion 2”
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 7
La respuesta es : ”El elemento x = 7 no se encuentra en elarreglo A”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 8: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/8.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Buscar un elemento en un arreglo ordenado
Problema:
Dado un arreglo ordenado de n numeros (A), queremos saber si elelemento x se encuentra en el. En caso de encontrarse, buscamosla posicion exacta de su primera aparicion.
Ejemplos:
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 6
La respuesta es : ”El elemento x = 6 se encuentra en elarreglo A por primera vez en la posicion 2”
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 7
La respuesta es :
”El elemento x = 7 no se encuentra en elarreglo A”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 9: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/9.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Buscar un elemento en un arreglo ordenado
Problema:
Dado un arreglo ordenado de n numeros (A), queremos saber si elelemento x se encuentra en el. En caso de encontrarse, buscamosla posicion exacta de su primera aparicion.
Ejemplos:
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 6
La respuesta es : ”El elemento x = 6 se encuentra en elarreglo A por primera vez en la posicion 2”
A = [01,
13,
26,
36,
48,
58,
610] y buscamos el elemento x = 7
La respuesta es : ”El elemento x = 7 no se encuentra en elarreglo A”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 10: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/10.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Posibles Soluciones
1 Busqueda lineal: Recorro el arreglo de izquierda a derecha,desde i = 0 hasta i = n − 1, y en cada posicion pregunto:”¿A[i ] = x?”
A = [01,
13,
26,
36,
48,
58,
610]
Complejidad: O(n)Si en algun momento encuentro una aparicion de x puedoreportarlo y terminar. Si para todo valor de i de 0 a n − 1tenemos que A[i ] 6= x , entonces reportamos que x no seencuentra en el arreglo.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 11: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/11.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Posibles Soluciones
1 Busqueda lineal:
Recorro el arreglo de izquierda a derecha,desde i = 0 hasta i = n − 1, y en cada posicion pregunto:”¿A[i ] = x?”
A = [01,
13,
26,
36,
48,
58,
610]
Complejidad: O(n)Si en algun momento encuentro una aparicion de x puedoreportarlo y terminar. Si para todo valor de i de 0 a n − 1tenemos que A[i ] 6= x , entonces reportamos que x no seencuentra en el arreglo.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 12: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/12.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Posibles Soluciones
1 Busqueda lineal: Recorro el arreglo de izquierda a derecha,desde i = 0 hasta i = n − 1, y en cada posicion pregunto:”¿A[i ] = x?”
A = [01,
13,
26,
36,
48,
58,
610]
Complejidad: O(n)Si en algun momento encuentro una aparicion de x puedoreportarlo y terminar. Si para todo valor de i de 0 a n − 1tenemos que A[i ] 6= x , entonces reportamos que x no seencuentra en el arreglo.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 13: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/13.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Posibles Soluciones
1 Busqueda lineal: Recorro el arreglo de izquierda a derecha,desde i = 0 hasta i = n − 1, y en cada posicion pregunto:”¿A[i ] = x?”
A = [01,
13,
26,
36,
48,
58,
610]
Complejidad: O(n)Si en algun momento encuentro una aparicion de x puedoreportarlo y terminar. Si para todo valor de i de 0 a n − 1tenemos que A[i ] 6= x , entonces reportamos que x no seencuentra en el arreglo.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 14: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/14.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Posibles Soluciones
1 Busqueda lineal: Recorro el arreglo de izquierda a derecha,desde i = 0 hasta i = n − 1, y en cada posicion pregunto:”¿A[i ] = x?”
A = [01↑
¿A[0]=6?
,13,
26,
36,
48,
58,
610]
Complejidad:
O(n)Si en algun momento encuentro una aparicion de x puedoreportarlo y terminar. Si para todo valor de i de 0 a n − 1tenemos que A[i ] 6= x , entonces reportamos que x no seencuentra en el arreglo.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 15: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/15.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Posibles Soluciones
1 Busqueda lineal: Recorro el arreglo de izquierda a derecha,desde i = 0 hasta i = n − 1, y en cada posicion pregunto:”¿A[i ] = x?”
A = [01,
13↑
¿A[1]=6?
,26,
36,
48,
58,
610]
Complejidad: O(n)Si en algun momento encuentro una aparicion de x puedoreportarlo y terminar. Si para todo valor de i de 0 a n − 1tenemos que A[i ] 6= x , entonces reportamos que x no seencuentra en el arreglo.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 16: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/16.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Posibles Soluciones
1 Busqueda lineal: Recorro el arreglo de izquierda a derecha,desde i = 0 hasta i = n − 1, y en cada posicion pregunto:”¿A[i ] = x?”
A = [01,
13,
26↑
¿A[2]=6?
,36,
48,
58,
610]
Complejidad: O(n)Si en algun momento encuentro una aparicion de x puedoreportarlo y terminar. Si para todo valor de i de 0 a n − 1tenemos que A[i ] 6= x , entonces reportamos que x no seencuentra en el arreglo.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 17: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/17.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Posibles Soluciones
1 Busqueda lineal: Recorro el arreglo de izquierda a derecha,desde i = 0 hasta i = n − 1, y en cada posicion pregunto:”¿A[i ] = x?”
A = [01,
13,
26↑
¿A[2]=6?
,36,
48,
58,
610]
Complejidad: O(n)Si en algun momento encuentro una aparicion de x puedoreportarlo y terminar. Si para todo valor de i de 0 a n − 1tenemos que A[i ] 6= x , entonces reportamos que x no seencuentra en el arreglo.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 18: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/18.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Posibles Soluciones
1 Busqueda lineal: Recorro el arreglo de izquierda a derecha,desde i = 0 hasta i = n − 1, y en cada posicion pregunto:”¿A[i ] = x?”
A = [01,
13,
26↑
¿A[2]=6?
,36,
48,
58,
610]
Complejidad: ...
Si en algun momento encuentro una aparicion de x puedoreportarlo y terminar. Si para todo valor de i de 0 a n − 1tenemos que A[i ] 6= x , entonces reportamos que x no seencuentra en el arreglo.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 19: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/19.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Posibles Soluciones
1 Busqueda lineal: Recorro el arreglo de izquierda a derecha,desde i = 0 hasta i = n − 1, y en cada posicion pregunto:”¿A[i ] = x?”
A = [01,
13,
26↑
¿A[2]=6?
,36,
48,
58,
610]
Complejidad: O(n)
Si en algun momento encuentro una aparicion de x puedoreportarlo y terminar. Si para todo valor de i de 0 a n − 1tenemos que A[i ] 6= x , entonces reportamos que x no seencuentra en el arreglo.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 20: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/20.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Posibles Soluciones
1 Busqueda lineal: Recorro el arreglo de izquierda a derecha,desde i = 0 hasta i = n − 1, y en cada posicion pregunto:”¿A[i ] = x?”
A = [01,
13,
26↑
¿A[2]=6?
,36,
48,
58,
610]
Complejidad: O(n)Si en algun momento encuentro una aparicion de x puedoreportarlo y terminar. Si para todo valor de i de 0 a n − 1tenemos que A[i ] 6= x , entonces reportamos que x no seencuentra en el arreglo.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 21: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/21.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Codigo
vector <int > A = {1,3,6,6,8,8,10};
// Busca x en A. Si esta , devuelve el indice
// Si no , devuelve -1
int busquedaLineal(int x, vector <int > &A)
{
int pos = -1, n = int(A.size ());
for (int i = 0; i < n; i++)
if (A[i] == x && pos == -1)
pos = i;
return pos;
}
¿Como podemos hacer que devuelva el ındice de la ultima aparicion?
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 22: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/22.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Codigo
vector <int > A = {1,3,6,6,8,8,10};
// Busca x en A. Si esta , devuelve el indice
// Si no , devuelve -1
int busquedaLineal(int x, vector <int > &A)
{
int pos = -1, n = int(A.size ());
for (int i = 0; i < n; i++)
if (A[i] == x && pos == -1)
pos = i;
return pos;
}
¿Como podemos hacer que devuelva el ındice de la ultima aparicion?
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 23: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/23.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 24: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/24.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 25: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/25.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).
La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 26: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/26.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 27: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/27.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 28: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/28.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610,
711,
813
¿A[8]<x?,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 29: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/29.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 30: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/30.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36
¿A[3]<x?,
48,
58,
610,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 31: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/31.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 32: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/32.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58
¿A[5]<x?,
610,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 33: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/33.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 34: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/34.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610
¿A[6]<x?,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 35: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/35.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 36: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/36.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610,
711
¿A[7]<x?,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 37: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/37.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
610,
711,
813,
914,
1015,
1115,
1217,
1318,
1418,
1520,
1621]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 38: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/38.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ahora, ¿que informacion no estamos utilizando del arreglo?
2 Busqueda Binaria: Usando que el arreglo esta ordenado,podemos aprovecharlo para encontrar el ındice de una maneramas rapida (en una menor cantidad de ”pasos” suponiendo elpeor caso).La idea sera mantener tres rangos. Uno con los numerosque sabemos que son menores, otro con los que sabemos queson mayores o iguales y otro donde no sabemos como secomparan con x . La idea es ir reduciendo el tamano de esteultimo rango a la mitad en cada paso. ¿Como podemoshacerlo?
Ejemplo: Buscamos el elemento x = 11
A = [01,
13,
26,
36,
48,
58,
↓6
10︸ ︷︷ ︸A[i ]<x
,
↓7
11,8
13,9
14,1015,
1115,
1217,
1318,
1418,
1520,
1621︸ ︷︷ ︸
A[i ]≥x
]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 39: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/39.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Codigo
int busquedaBinaria (int x, vector <int > &A){
int n = int(A.size ());int a = -1, b = n; // de a para atras <while (b-a > 1) // de b para adelante >={ // [a+1...b-1] : RANGO ACTIVO
int medio = (a+b)/2; // punto medio de [a..b]if (A[medio] < x)
a = medio;else
b = medio;}if (b < n && A[b] == x) // a = 6, b = 7
return b; // en el ejemplo anteriorelse
return -1;}
Complejidad : . . .
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 40: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/40.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Codigo
int busquedaBinaria (int x, vector <int > &A){
int n = int(A.size ());int a = -1, b = n; // de a para atras <while (b-a > 1) // de b para adelante >={ // [a+1...b-1] : RANGO ACTIVO
int medio = (a+b)/2; // punto medio de [a..b]if (A[medio] < x)
a = medio;else
b = medio;}if (b < n && A[b] == x) // a = 6, b = 7
return b; // en el ejemplo anteriorelse
return -1;}
Complejidad : . . .Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 41: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/41.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Codigo
int busquedaBinaria (int x, vector <int > &A){
int n = int(A.size ());int a = -1, b = n; // de a para atras <while (b-a > 1) // de b para adelante >={ // [a+1...b-1] : RANGO ACTIVO
int medio = (a+b)/2; // punto medio de [a..b]if (A[medio] < x)
a = medio;else
b = medio;}if (b < n && A[b] == x) // a = 6, b = 7
return b; // en el ejemplo anteriorelse
return -1;}
Complejidad : O (lg(n))Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 42: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/42.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Propiedades Binarias
Ahora vamos a utilizar esta misma idea para resolver masproblemas, y no solo : ”Como buscar un numero en un arregloordenado”.Supongamos que tenemos una cierta propiedad que depende deun valor. Llamemosla P(k). Por ejemplo: P(k) : k2 > 29. Nosqueda que para un cierto k , P(k) puede ser Verdadera o Falsa.
P(1) : 12 > 29 ⇐⇒ 1 > 29→ Falsa
P(2) : 22 > 29 ⇐⇒ 4 > 29→ Falsa
P(3) : 32 > 29 ⇐⇒ 9 > 29→ Falsa
P(4) : 42 > 29 ⇐⇒ 16 > 29→ Falsa
P(5) : 52 > 29 ⇐⇒ 25 > 29→ Falsa
P(6) : 62 > 29 ⇐⇒ 36 > 29→ Verdadera
P(7) : 72 > 29 ⇐⇒ 49 > 29→ Verdadera
P(8) : 82 > 29 ⇐⇒ 64 > 29→ Verdadera
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 43: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/43.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Propiedades Binarias
Ahora vamos a utilizar esta misma idea para resolver masproblemas, y no solo : ”Como buscar un numero en un arregloordenado”.
Supongamos que tenemos una cierta propiedad que depende deun valor. Llamemosla P(k). Por ejemplo: P(k) : k2 > 29. Nosqueda que para un cierto k , P(k) puede ser Verdadera o Falsa.
P(1) : 12 > 29 ⇐⇒ 1 > 29→ Falsa
P(2) : 22 > 29 ⇐⇒ 4 > 29→ Falsa
P(3) : 32 > 29 ⇐⇒ 9 > 29→ Falsa
P(4) : 42 > 29 ⇐⇒ 16 > 29→ Falsa
P(5) : 52 > 29 ⇐⇒ 25 > 29→ Falsa
P(6) : 62 > 29 ⇐⇒ 36 > 29→ Verdadera
P(7) : 72 > 29 ⇐⇒ 49 > 29→ Verdadera
P(8) : 82 > 29 ⇐⇒ 64 > 29→ Verdadera
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 44: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/44.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Propiedades Binarias
Ahora vamos a utilizar esta misma idea para resolver masproblemas, y no solo : ”Como buscar un numero en un arregloordenado”.Supongamos que tenemos una cierta propiedad que depende deun valor. Llamemosla P(k). Por ejemplo: P(k) : k2 > 29. Nosqueda que para un cierto k , P(k) puede ser Verdadera o Falsa.
P(1) : 12 > 29 ⇐⇒ 1 > 29→ Falsa
P(2) : 22 > 29 ⇐⇒ 4 > 29→ Falsa
P(3) : 32 > 29 ⇐⇒ 9 > 29→ Falsa
P(4) : 42 > 29 ⇐⇒ 16 > 29→ Falsa
P(5) : 52 > 29 ⇐⇒ 25 > 29→ Falsa
P(6) : 62 > 29 ⇐⇒ 36 > 29→ Verdadera
P(7) : 72 > 29 ⇐⇒ 49 > 29→ Verdadera
P(8) : 82 > 29 ⇐⇒ 64 > 29→ Verdadera
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 45: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/45.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Propiedades Binarias
Ahora vamos a utilizar esta misma idea para resolver masproblemas, y no solo : ”Como buscar un numero en un arregloordenado”.Supongamos que tenemos una cierta propiedad que depende deun valor. Llamemosla P(k). Por ejemplo: P(k) : k2 > 29. Nosqueda que para un cierto k , P(k) puede ser Verdadera o Falsa.
P(1) : 12 > 29 ⇐⇒ 1 > 29→ Falsa
P(2) : 22 > 29 ⇐⇒ 4 > 29→ Falsa
P(3) : 32 > 29 ⇐⇒ 9 > 29→ Falsa
P(4) : 42 > 29 ⇐⇒ 16 > 29→ Falsa
P(5) : 52 > 29 ⇐⇒ 25 > 29→ Falsa
P(6) : 62 > 29 ⇐⇒ 36 > 29→ Verdadera
P(7) : 72 > 29 ⇐⇒ 49 > 29→ Verdadera
P(8) : 82 > 29 ⇐⇒ 64 > 29→ Verdadera
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 46: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/46.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Propiedades Binarias
Si nuestra propiedad cumple que es Verdadera hasta un ciertopunto y luego es siempre Falsa (o al reves, Falsa hasta un ciertopunto y luego Verdadera), decimos que es una propiedad binaria.En estos casos, podemos hacer busqueda binaria, para encontrarel momento en el que cambia de valor nuestra propiedad.
k 0 1 . . . a b b+1 . . . n
P(k) Falsa Falsa Falsa Falsa Verdad Verdad Verdad Verdad
Busqueda binaria nos permite encontrar el primer momento enque nuestra propiedad resulta ser verdadera ası como el ultimomomento en que nuestra propiedad es falsa (O al reves,dependiendo de que propiedad planteamos).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 47: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/47.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Propiedades Binarias
Si nuestra propiedad cumple que es Verdadera hasta un ciertopunto y luego es siempre Falsa (o al reves, Falsa hasta un ciertopunto y luego Verdadera), decimos que es una propiedad binaria.
En estos casos, podemos hacer busqueda binaria, para encontrarel momento en el que cambia de valor nuestra propiedad.
k 0 1 . . . a b b+1 . . . n
P(k) Falsa Falsa Falsa Falsa Verdad Verdad Verdad Verdad
Busqueda binaria nos permite encontrar el primer momento enque nuestra propiedad resulta ser verdadera ası como el ultimomomento en que nuestra propiedad es falsa (O al reves,dependiendo de que propiedad planteamos).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 48: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/48.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Propiedades Binarias
Si nuestra propiedad cumple que es Verdadera hasta un ciertopunto y luego es siempre Falsa (o al reves, Falsa hasta un ciertopunto y luego Verdadera), decimos que es una propiedad binaria.En estos casos, podemos hacer busqueda binaria, para encontrarel momento en el que cambia de valor nuestra propiedad.
k 0 1 . . . a b b+1 . . . n
P(k) Falsa Falsa Falsa Falsa Verdad Verdad Verdad Verdad
Busqueda binaria nos permite encontrar el primer momento enque nuestra propiedad resulta ser verdadera ası como el ultimomomento en que nuestra propiedad es falsa (O al reves,dependiendo de que propiedad planteamos).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 49: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/49.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Propiedades Binarias
Si nuestra propiedad cumple que es Verdadera hasta un ciertopunto y luego es siempre Falsa (o al reves, Falsa hasta un ciertopunto y luego Verdadera), decimos que es una propiedad binaria.En estos casos, podemos hacer busqueda binaria, para encontrarel momento en el que cambia de valor nuestra propiedad.
k 0 1 . . . a b b+1 . . . n
P(k) Falsa Falsa Falsa Falsa Verdad Verdad Verdad Verdad
Busqueda binaria nos permite encontrar el primer momento enque nuestra propiedad resulta ser verdadera ası como el ultimomomento en que nuestra propiedad es falsa (O al reves,dependiendo de que propiedad planteamos).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 50: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/50.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Propiedades Binarias
Si nuestra propiedad cumple que es Verdadera hasta un ciertopunto y luego es siempre Falsa (o al reves, Falsa hasta un ciertopunto y luego Verdadera), decimos que es una propiedad binaria.En estos casos, podemos hacer busqueda binaria, para encontrarel momento en el que cambia de valor nuestra propiedad.
k 0 1 . . . a b b+1 . . . n
P(k) Falsa Falsa Falsa Falsa Verdad Verdad Verdad Verdad
Busqueda binaria nos permite encontrar el primer momento enque nuestra propiedad resulta ser verdadera ası como el ultimomomento en que nuestra propiedad es falsa (O al reves,dependiendo de que propiedad planteamos).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 51: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/51.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Propiedades Binarias
Codigo
¿Es muy distinto el codigo al anterior? NO
void busquedaBinaria (int &a, int &b)
{ // P(a) : Falso
while (b-a > 1) // P(b) : Verdadero
{ // [a+1...b-1] : RANGO ACTIVO
int medio = (a+b)/2; // punto medio de [a..b]
if (P(medio)) // P(medio) == true
b = medio;
else
a = medio;
}
// Ahora en a queda el ultimo que es Falso
// Y en b queda el primero que es Verdadero
}
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 52: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/52.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Propiedades Binarias
Codigo
¿Es muy distinto el codigo al anterior?
void busquedaBinaria (int &a, int &b)
{ // P(a) : Falso
while (b-a > 1) // P(b) : Verdadero
{ // [a+1...b-1] : RANGO ACTIVO
int medio = (a+b)/2; // punto medio de [a..b]
if (P(medio)) // P(medio) == true
b = medio;
else
a = medio;
}
// Ahora en a queda el ultimo que es Falso
// Y en b queda el primero que es Verdadero
}
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 53: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/53.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Propiedades Binarias
Codigo
¿Es muy distinto el codigo al anterior? NO
void busquedaBinaria (int &a, int &b)
{ // P(a) : Falso
while (b-a > 1) // P(b) : Verdadero
{ // [a+1...b-1] : RANGO ACTIVO
int medio = (a+b)/2; // punto medio de [a..b]
if (P(medio)) // P(medio) == true
b = medio;
else
a = medio;
}
// Ahora en a queda el ultimo que es Falso
// Y en b queda el primero que es Verdadero
}
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 54: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/54.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Evolucionando Pokemones
Ash acaba de atrapar N pokemones. El tiene a su disposicion Mbarras de caramelo. Evolucionar a un pokemon, le cuesta Xbarras de caramelo. A su vez, puede vender a un pokemon y recibira cambio Y barras de caramelo. ¿Cual es la maxima cantidad depokemones que puede evolucionar?
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 55: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/55.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Evolucionando Pokemones
Ash acaba de atrapar N pokemones. El tiene a su disposicion Mbarras de caramelo. Evolucionar a un pokemon, le cuesta Xbarras de caramelo. A su vez, puede vender a un pokemon y recibira cambio Y barras de caramelo. ¿Cual es la maxima cantidad depokemones que puede evolucionar?
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 56: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/56.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Evolucionando Pokemones
Ash acaba de atrapar N pokemones. El tiene a su disposicion Mbarras de caramelo. Evolucionar a un pokemon, le cuesta Xbarras de caramelo. A su vez, puede vender a un pokemon y recibira cambio Y barras de caramelo. ¿Cual es la maxima cantidad depokemones que puede evolucionar?
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 57: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/57.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Observacion clave
Si fijamos la cantidad de pokemones que vamos aevolucionar, digamos k con 0 ≤ k ≤ N. Entonces podemosvender a los N − k pokemones que no vamos a evolucionar. Conesto, disponemos de M + (N − k) · Y barras de caramelo.Para evolucionar a los k pokemones, necesitamos tener al menosk · X barras de caramelos. O sea, debe valer que:
k · X ≤ (N − k) · Y + M
1 Solucion: Probar todos los valores de k entre 0 y N(inclusive), y tomar el de mayor valor que satisfaga lacondicion. Complejidad : O(N)
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 58: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/58.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Observacion clave
Si fijamos la cantidad de pokemones que vamos aevolucionar, digamos k con 0 ≤ k ≤ N. Entonces podemosvender a los N − k pokemones que no vamos a evolucionar. Conesto, disponemos de M + (N − k) · Y barras de caramelo.Para evolucionar a los k pokemones, necesitamos tener al menosk · X barras de caramelos. O sea, debe valer que:
k · X ≤ (N − k) · Y + M
1 Solucion: Probar todos los valores de k entre 0 y N(inclusive), y tomar el de mayor valor que satisfaga lacondicion. Complejidad : O(N)
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 59: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/59.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Observacion clave
Si fijamos la cantidad de pokemones que vamos aevolucionar, digamos k con 0 ≤ k ≤ N. Entonces podemosvender a los N − k pokemones que no vamos a evolucionar. Conesto, disponemos de M + (N − k) · Y barras de caramelo.Para evolucionar a los k pokemones, necesitamos tener al menosk · X barras de caramelos. O sea, debe valer que:
k · X ≤ (N − k) · Y + M
1 Solucion: Probar todos los valores de k entre 0 y N(inclusive), y tomar el de mayor valor que satisfaga lacondicion. Complejidad : O(N)
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 60: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/60.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
2 Solucion: Notemos que si podemos evolucionar kpokemones, tambien podemos evolucionar k − 1, k − 2,. . . , 0 pokemones. En particular siempre podemosevolucionar 0 pokemones.Ademas, si no podemos evolucionar k pokemones, menosaun podremos evolucionar k + 1, o k + 2 pokemones (ocualquier otro numero mayor). En particular nunca podremosevolucionar N + 1 pokemones.Entonces, tomando como propiedad:P(k) : ”Puedo evolucionar k pokemones”, podemos hacerbusqueda binaria en la propiedad P.Complejidad: O(lg(N))
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 61: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/61.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
2 Solucion: Notemos que si podemos evolucionar kpokemones, tambien podemos evolucionar k − 1, k − 2,. . . , 0 pokemones. En particular siempre podemosevolucionar 0 pokemones.Ademas, si no podemos evolucionar k pokemones, menosaun podremos evolucionar k + 1, o k + 2 pokemones (ocualquier otro numero mayor). En particular nunca podremosevolucionar N + 1 pokemones.
Entonces, tomando como propiedad:P(k) : ”Puedo evolucionar k pokemones”, podemos hacerbusqueda binaria en la propiedad P.Complejidad: O(lg(N))
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 62: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/62.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
2 Solucion: Notemos que si podemos evolucionar kpokemones, tambien podemos evolucionar k − 1, k − 2,. . . , 0 pokemones. En particular siempre podemosevolucionar 0 pokemones.Ademas, si no podemos evolucionar k pokemones, menosaun podremos evolucionar k + 1, o k + 2 pokemones (ocualquier otro numero mayor). En particular nunca podremosevolucionar N + 1 pokemones.Entonces, tomando como propiedad:P(k) : ”Puedo evolucionar k pokemones”, podemos hacerbusqueda binaria en la propiedad P.
Complejidad: O(lg(N))
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 63: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/63.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
2 Solucion: Notemos que si podemos evolucionar kpokemones, tambien podemos evolucionar k − 1, k − 2,. . . , 0 pokemones. En particular siempre podemosevolucionar 0 pokemones.Ademas, si no podemos evolucionar k pokemones, menosaun podremos evolucionar k + 1, o k + 2 pokemones (ocualquier otro numero mayor). En particular nunca podremosevolucionar N + 1 pokemones.Entonces, tomando como propiedad:P(k) : ”Puedo evolucionar k pokemones”, podemos hacerbusqueda binaria en la propiedad P.Complejidad: O(lg(N))
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 64: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/64.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
3 Sabemos que 0 ≤ k ≤ N. Y de la condicion vista, podemosdespejar una inecuacion para k :
k · X ≤ (N − k) · Y + M ⇐⇒k · X ≤ N · Y − k · Y + M ⇐⇒
k · X + k · Y ≤ N · Y + M ⇐⇒k · (X + Y ) ≤ N · Y + M ⇐⇒
k ≤ N · Y + M
X + Y
Por lo tanto, la respuesta sera :
min
(N,
⌊N · Y + M
X + Y
⌋)Complejidad: O(1)
https://csacademy.com/contest/archive/task/pokemon-evolution
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 65: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/65.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
3 Sabemos que 0 ≤ k ≤ N. Y de la condicion vista, podemosdespejar una inecuacion para k :
k · X ≤ (N − k) · Y + M ⇐⇒k · X ≤ N · Y − k · Y + M ⇐⇒
k · X + k · Y ≤ N · Y + M ⇐⇒k · (X + Y ) ≤ N · Y + M ⇐⇒
k ≤ N · Y + M
X + Y
Por lo tanto, la respuesta sera :
min
(N,
⌊N · Y + M
X + Y
⌋)Complejidad: O(1)
https://csacademy.com/contest/archive/task/pokemon-evolution
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 66: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/66.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
3 Sabemos que 0 ≤ k ≤ N. Y de la condicion vista, podemosdespejar una inecuacion para k :
k · X ≤ (N − k) · Y + M ⇐⇒k · X ≤ N · Y − k · Y + M ⇐⇒
k · X + k · Y ≤ N · Y + M ⇐⇒k · (X + Y ) ≤ N · Y + M ⇐⇒
k ≤ N · Y + M
X + Y
Por lo tanto, la respuesta sera :
min
(N,
⌊N · Y + M
X + Y
⌋)Complejidad: O(1)
https://csacademy.com/contest/archive/task/pokemon-evolution
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 67: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/67.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
3 Sabemos que 0 ≤ k ≤ N. Y de la condicion vista, podemosdespejar una inecuacion para k :
k · X ≤ (N − k) · Y + M ⇐⇒k · X ≤ N · Y − k · Y + M ⇐⇒
k · X + k · Y ≤ N · Y + M ⇐⇒k · (X + Y ) ≤ N · Y + M ⇐⇒
k ≤ N · Y + M
X + Y
Por lo tanto, la respuesta sera :
min
(N,
⌊N · Y + M
X + Y
⌋)
Complejidad: O(1)
https://csacademy.com/contest/archive/task/pokemon-evolution
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 68: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/68.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
3 Sabemos que 0 ≤ k ≤ N. Y de la condicion vista, podemosdespejar una inecuacion para k :
k · X ≤ (N − k) · Y + M ⇐⇒k · X ≤ N · Y − k · Y + M ⇐⇒
k · X + k · Y ≤ N · Y + M ⇐⇒k · (X + Y ) ≤ N · Y + M ⇐⇒
k ≤ N · Y + M
X + Y
Por lo tanto, la respuesta sera :
min
(N,
⌊N · Y + M
X + Y
⌋)Complejidad: O(1)
https://csacademy.com/contest/archive/task/pokemon-evolution
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 69: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/69.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
3 Sabemos que 0 ≤ k ≤ N. Y de la condicion vista, podemosdespejar una inecuacion para k :
k · X ≤ (N − k) · Y + M ⇐⇒k · X ≤ N · Y − k · Y + M ⇐⇒
k · X + k · Y ≤ N · Y + M ⇐⇒k · (X + Y ) ≤ N · Y + M ⇐⇒
k ≤ N · Y + M
X + Y
Por lo tanto, la respuesta sera :
min
(N,
⌊N · Y + M
X + Y
⌋)Complejidad: O(1)
https://csacademy.com/contest/archive/task/pokemon-evolution
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 70: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/70.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Problema de Optimizacion → Problema de Decision
En este problema que vimos aparece un patron que es comun enlos problemas que se resuelven con busqueda binaria.
Lo que hicimos fue convertir un problema de optimizacion(¿cual es la maxima cantidad de pokemones que podemosevolucionar?), en uno de decision (Sı/No) (¿Puedo evolucionark pokemones?).
Veamos mas ejemplos.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 71: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/71.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Problema de Optimizacion → Problema de Decision
En este problema que vimos aparece un patron que es comun enlos problemas que se resuelven con busqueda binaria.
Lo que hicimos fue convertir un problema de optimizacion(¿cual es la maxima cantidad de pokemones que podemosevolucionar?), en uno de decision (Sı/No) (¿Puedo evolucionark pokemones?).
Veamos mas ejemplos.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 72: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/72.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Maximo Cuadrado en un Tablero
Tenemos un tablero de m × n (m filas y n columnas). Algunascasillas del tablero estan pintadas de blanco y otras de negro.Buscamos encontrar el tamano del lado del subtablero cuadradomas grande de casillas negras.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 73: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/73.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Maximo Cuadrado en un Tablero
Tenemos un tablero de m × n (m filas y n columnas). Algunascasillas del tablero estan pintadas de blanco y otras de negro.Buscamos encontrar el tamano del lado del subtablero cuadradomas grande de casillas negras.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 74: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/74.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Maximo Cuadrado en un Tablero
Tenemos un tablero de m × n (m filas y n columnas). Algunascasillas del tablero estan pintadas de blanco y otras de negro.Buscamos encontrar el tamano del lado del subtablero cuadradomas grande de casillas negras.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 75: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/75.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Cosas que vamos a usar
Supongamos que tenemos una funcion booleana f (k , i , j) que nos dice si hayun cuadrado de casillas negras de lado k en el tablero cuya casilla superior
izquierda esta situada en la fila i y la columna j . Por ejemplo, en la imagen
anterior, f (2, 2, 2) es true y f (3, 2, 2) es false.
1 Solucion: El tamano del cuadrado que buscamos es a lo sumo tangrande como la dimension mas chica del tablero. Podemos recorrertodas las casillas, y en cada una preguntarle a la funcion f si existe un
tablero de tamano 0, 1, 2, . . . ,min(n,m) inclusive. El valor mas grande
que devolvio true sera el lado del cuadrado mas grande que tiene la
esquina superior izquierda en la casilla que estamos analizando. Tomando
el maximo de este numero para todas las casillas resolvemos el problema.
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m ·min(n,m) ∼ n3
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 76: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/76.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Cosas que vamos a usar
Supongamos que tenemos una funcion booleana f (k , i , j) que nos dice si hayun cuadrado de casillas negras de lado k en el tablero cuya casilla superior
izquierda esta situada en la fila i y la columna j . Por ejemplo, en la imagen
anterior, f (2, 2, 2) es true y f (3, 2, 2) es false.
1 Solucion: El tamano del cuadrado que buscamos es a lo sumo tangrande como la dimension mas chica del tablero. Podemos recorrertodas las casillas, y en cada una preguntarle a la funcion f si existe un
tablero de tamano 0, 1, 2, . . . ,min(n,m) inclusive. El valor mas grande
que devolvio true sera el lado del cuadrado mas grande que tiene la
esquina superior izquierda en la casilla que estamos analizando. Tomando
el maximo de este numero para todas las casillas resolvemos el problema.
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m ·min(n,m) ∼ n3
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 77: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/77.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Cosas que vamos a usar
Supongamos que tenemos una funcion booleana f (k , i , j) que nos dice si hayun cuadrado de casillas negras de lado k en el tablero cuya casilla superior
izquierda esta situada en la fila i y la columna j . Por ejemplo, en la imagen
anterior, f (2, 2, 2) es true y f (3, 2, 2) es false.
1 Solucion: El tamano del cuadrado que buscamos es a lo sumo tangrande como la dimension mas chica del tablero. Podemos recorrertodas las casillas, y en cada una preguntarle a la funcion f si existe un
tablero de tamano 0, 1, 2, . . . ,min(n,m) inclusive. El valor mas grande
que devolvio true sera el lado del cuadrado mas grande que tiene la
esquina superior izquierda en la casilla que estamos analizando. Tomando
el maximo de este numero para todas las casillas resolvemos el problema.
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m ·min(n,m) ∼ n3
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 78: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/78.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Cosas que vamos a usar
Supongamos que tenemos una funcion booleana f (k , i , j) que nos dice si hayun cuadrado de casillas negras de lado k en el tablero cuya casilla superior
izquierda esta situada en la fila i y la columna j . Por ejemplo, en la imagen
anterior, f (2, 2, 2) es true y f (3, 2, 2) es false.
1 Solucion: El tamano del cuadrado que buscamos es a lo sumo tangrande como la dimension mas chica del tablero. Podemos recorrertodas las casillas, y en cada una preguntarle a la funcion f si existe un
tablero de tamano 0, 1, 2, . . . ,min(n,m) inclusive. El valor mas grande
que devolvio true sera el lado del cuadrado mas grande que tiene la
esquina superior izquierda en la casilla que estamos analizando. Tomando
el maximo de este numero para todas las casillas resolvemos el problema.
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m ·min(n,m) ∼ n3
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 79: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/79.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Cosas que vamos a usar
Supongamos que tenemos una funcion booleana f (k , i , j) que nos dice si hayun cuadrado de casillas negras de lado k en el tablero cuya casilla superior
izquierda esta situada en la fila i y la columna j . Por ejemplo, en la imagen
anterior, f (2, 2, 2) es true y f (3, 2, 2) es false.
1 Solucion: El tamano del cuadrado que buscamos es a lo sumo tangrande como la dimension mas chica del tablero. Podemos recorrertodas las casillas, y en cada una preguntarle a la funcion f si existe un
tablero de tamano 0, 1, 2, . . . ,min(n,m) inclusive. El valor mas grande
que devolvio true sera el lado del cuadrado mas grande que tiene la
esquina superior izquierda en la casilla que estamos analizando. Tomando
el maximo de este numero para todas las casillas resolvemos el problema.
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m ·min(n,m) ∼ n3
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 80: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/80.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
¿Como podemos acelerar la solucion? (hacer menos llamados ala f )Busqueda binaria Ok... ¿Pero en que?
2 En la solucion anterior, cuando estamos parados en unacasilla, podemos hacer busqueda binaria en el lado delcuadrado que buscamos. ¿Por que?Supongamos que desde una casilla hay un subtablero detamano k × k , entonces desde esa misma casilla es claro quetambien hay subtableros de lado k − 1, k − 2, etc. Por otrolado, si no hay un subtablero de lado k , tampoco habra unode lado k + 1 o mas. (hacer siempre dibujitos).
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m · lg (min(n,m)) ∼ n2 · lg(n)
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 81: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/81.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
¿Como podemos acelerar la solucion? (hacer menos llamados ala f )
Busqueda binaria Ok... ¿Pero en que?
2 En la solucion anterior, cuando estamos parados en unacasilla, podemos hacer busqueda binaria en el lado delcuadrado que buscamos. ¿Por que?Supongamos que desde una casilla hay un subtablero detamano k × k , entonces desde esa misma casilla es claro quetambien hay subtableros de lado k − 1, k − 2, etc. Por otrolado, si no hay un subtablero de lado k , tampoco habra unode lado k + 1 o mas. (hacer siempre dibujitos).
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m · lg (min(n,m)) ∼ n2 · lg(n)
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 82: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/82.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
¿Como podemos acelerar la solucion? (hacer menos llamados ala f )Busqueda binaria
Ok... ¿Pero en que?
2 En la solucion anterior, cuando estamos parados en unacasilla, podemos hacer busqueda binaria en el lado delcuadrado que buscamos. ¿Por que?Supongamos que desde una casilla hay un subtablero detamano k × k , entonces desde esa misma casilla es claro quetambien hay subtableros de lado k − 1, k − 2, etc. Por otrolado, si no hay un subtablero de lado k , tampoco habra unode lado k + 1 o mas. (hacer siempre dibujitos).
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m · lg (min(n,m)) ∼ n2 · lg(n)
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 83: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/83.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
¿Como podemos acelerar la solucion? (hacer menos llamados ala f )Busqueda binaria Ok... ¿Pero en que?
2 En la solucion anterior, cuando estamos parados en unacasilla, podemos hacer busqueda binaria en el lado delcuadrado que buscamos. ¿Por que?Supongamos que desde una casilla hay un subtablero detamano k × k , entonces desde esa misma casilla es claro quetambien hay subtableros de lado k − 1, k − 2, etc. Por otrolado, si no hay un subtablero de lado k , tampoco habra unode lado k + 1 o mas. (hacer siempre dibujitos).
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m · lg (min(n,m)) ∼ n2 · lg(n)
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 84: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/84.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
¿Como podemos acelerar la solucion? (hacer menos llamados ala f )Busqueda binaria Ok... ¿Pero en que?
2 En la solucion anterior, cuando estamos parados en unacasilla, podemos hacer busqueda binaria en el lado delcuadrado que buscamos. ¿Por que?
Supongamos que desde una casilla hay un subtablero detamano k × k , entonces desde esa misma casilla es claro quetambien hay subtableros de lado k − 1, k − 2, etc. Por otrolado, si no hay un subtablero de lado k , tampoco habra unode lado k + 1 o mas. (hacer siempre dibujitos).
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m · lg (min(n,m)) ∼ n2 · lg(n)
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 85: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/85.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
¿Como podemos acelerar la solucion? (hacer menos llamados ala f )Busqueda binaria Ok... ¿Pero en que?
2 En la solucion anterior, cuando estamos parados en unacasilla, podemos hacer busqueda binaria en el lado delcuadrado que buscamos. ¿Por que?Supongamos que desde una casilla hay un subtablero detamano k × k , entonces desde esa misma casilla es claro quetambien hay subtableros de lado k − 1, k − 2, etc. Por otrolado, si no hay un subtablero de lado k , tampoco habra unode lado k + 1 o mas. (hacer siempre dibujitos).
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m · lg (min(n,m)) ∼ n2 · lg(n)
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 86: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/86.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
¿Como podemos acelerar la solucion? (hacer menos llamados ala f )Busqueda binaria Ok... ¿Pero en que?
2 En la solucion anterior, cuando estamos parados en unacasilla, podemos hacer busqueda binaria en el lado delcuadrado que buscamos. ¿Por que?Supongamos que desde una casilla hay un subtablero detamano k × k , entonces desde esa misma casilla es claro quetambien hay subtableros de lado k − 1, k − 2, etc. Por otrolado, si no hay un subtablero de lado k , tampoco habra unode lado k + 1 o mas. (hacer siempre dibujitos).
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m · lg (min(n,m)) ∼ n2 · lg(n)
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 87: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/87.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
¿Como podemos acelerar la solucion? (hacer menos llamados ala f )Busqueda binaria Ok... ¿Pero en que?
2 En la solucion anterior, cuando estamos parados en unacasilla, podemos hacer busqueda binaria en el lado delcuadrado que buscamos. ¿Por que?Supongamos que desde una casilla hay un subtablero detamano k × k , entonces desde esa misma casilla es claro quetambien hay subtableros de lado k − 1, k − 2, etc. Por otrolado, si no hay un subtablero de lado k , tampoco habra unode lado k + 1 o mas. (hacer siempre dibujitos).
¿Cuantas veces estamos llamando a la funcion f ?
Respuesta : n ·m · lg (min(n,m)) ∼ n2 · lg(n)
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 88: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/88.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Codigo
int cuadradoEnTablero (vector <vector <int > > &tablero)
{
int respuesta = 0; // siempre hay cuadrado de lado 0.
int m = int(tablero.size()), n = int(tablero [0]. size ()); // filas
for (int i = 0; i < m; i++) // y columnas
for (int j = 0; j < n; j++)
{
int a = 0, b = min(n,m)+1; // Hay cuadrado de lado 0,
while (b-a > 1) // No hay cuadrado de lado min(n,m)+1
{
int k = (a+b)/2;
if (f(k,i,j,tablero )) // f(k,i,j,tablero) == true
a = k;
else
b = k;
} // En a queda guardado el lado del cuadrado
// mas grande que existe desde la casilla (i,j)
respuesta = max(respuesta ,a);
}
return respuesta;
}
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 89: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/89.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Problema
Petr vive en un pueblo de Rusia. Las rutas de su paıs tienen un”ındice de peligrosidad”. Petr quiere viajar del pueblo A (donde elvive) a B (donde vive su mejor amigo), minimizando el ındice depeligrosidad de la ruta mas peligrosa que usa en su camino.
Por ejemplo, en el pueblo de la figura, lo mejor es tomar el camino
A2→ E
4→ F3→ B, cuya ruta mas peligrosa es de 4.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 90: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/90.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Problema
Petr vive en un pueblo de Rusia. Las rutas de su paıs tienen un”ındice de peligrosidad”. Petr quiere viajar del pueblo A (donde elvive) a B (donde vive su mejor amigo), minimizando el ındice depeligrosidad de la ruta mas peligrosa que usa en su camino.
Por ejemplo, en el pueblo de la figura, lo mejor es tomar el camino
A2→ E
4→ F3→ B, cuya ruta mas peligrosa es de 4.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 91: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/91.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Si bien hay muchas formas de resolver el problema, vamos ahacerlo con Busqueda BinariaSi fijamos el valor de la ruta mas peligrosa a utilizar, digamosque la ruta mas peligrosa que usamos tiene ındice de peligrosidadx (y descartamos todas las rutas con peligrosidad mayor a x).Entonces si en este nuevo diseno de paıs hay un camino(cualquiera) de A a B, sabemos que existe un camino cuya rutamas peligrosa es a lo sumo x .Si consideramos la propiedad P(x) : ”Hay un camino entre A y Bcuya ruta mas peligrosa es menor o igual a x ”, entonces estapropiedad es binaria. ¿Por que?Si tenemos un camino cuya ruta mas peligrosa tiene peligrosidadmenor o igual a x , entonces tenemos un camino cuya ruta maspeligrosa es menor o igual a x + 1, . . . (el mismo camino funciona).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 92: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/92.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Si bien hay muchas formas de resolver el problema, vamos ahacerlo con Busqueda Binaria
Si fijamos el valor de la ruta mas peligrosa a utilizar, digamosque la ruta mas peligrosa que usamos tiene ındice de peligrosidadx (y descartamos todas las rutas con peligrosidad mayor a x).Entonces si en este nuevo diseno de paıs hay un camino(cualquiera) de A a B, sabemos que existe un camino cuya rutamas peligrosa es a lo sumo x .Si consideramos la propiedad P(x) : ”Hay un camino entre A y Bcuya ruta mas peligrosa es menor o igual a x ”, entonces estapropiedad es binaria. ¿Por que?Si tenemos un camino cuya ruta mas peligrosa tiene peligrosidadmenor o igual a x , entonces tenemos un camino cuya ruta maspeligrosa es menor o igual a x + 1, . . . (el mismo camino funciona).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 93: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/93.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Si bien hay muchas formas de resolver el problema, vamos ahacerlo con Busqueda BinariaSi fijamos el valor de la ruta mas peligrosa a utilizar, digamosque la ruta mas peligrosa que usamos tiene ındice de peligrosidadx (y descartamos todas las rutas con peligrosidad mayor a x).Entonces si en este nuevo diseno de paıs hay un camino(cualquiera) de A a B, sabemos que existe un camino cuya rutamas peligrosa es a lo sumo x .Si consideramos la propiedad P(x) : ”Hay un camino entre A y Bcuya ruta mas peligrosa es menor o igual a x ”, entonces estapropiedad es binaria. ¿Por que?
Si tenemos un camino cuya ruta mas peligrosa tiene peligrosidadmenor o igual a x , entonces tenemos un camino cuya ruta maspeligrosa es menor o igual a x + 1, . . . (el mismo camino funciona).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 94: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/94.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Si bien hay muchas formas de resolver el problema, vamos ahacerlo con Busqueda BinariaSi fijamos el valor de la ruta mas peligrosa a utilizar, digamosque la ruta mas peligrosa que usamos tiene ındice de peligrosidadx (y descartamos todas las rutas con peligrosidad mayor a x).Entonces si en este nuevo diseno de paıs hay un camino(cualquiera) de A a B, sabemos que existe un camino cuya rutamas peligrosa es a lo sumo x .Si consideramos la propiedad P(x) : ”Hay un camino entre A y Bcuya ruta mas peligrosa es menor o igual a x ”, entonces estapropiedad es binaria. ¿Por que?Si tenemos un camino cuya ruta mas peligrosa tiene peligrosidadmenor o igual a x , entonces tenemos un camino cuya ruta maspeligrosa es menor o igual a x + 1, . . . (el mismo camino funciona).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 95: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/95.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Ejemplo grafico
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 96: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/96.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Ejemplo grafico
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 97: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/97.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Ejemplo grafico
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 98: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/98.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Ejemplo grafico
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 99: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/99.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Ejemplo grafico
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 100: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/100.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Ejemplo grafico
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 101: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/101.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Ejemplo grafico
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 102: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/102.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Problemas de Tarea
Problemas (en orden creciente de dificultad (subjetivo))
”Frodo y sus almohadas”http://codeforces.com/problemset/problem/760/B
”Buen kilo de pan flauta”http://www.spoj.com/problems/TAP2015B/
”Anton y el cuento de hadas”http://codeforces.com/problemset/problem/785/C
”Dinosaur menace” (difıcil)http://www.spoj.com/problems/DINOSM/
Siempre pueden hacer consultas sobre problemas (o cualquier temarelacionado con la Olimpıada) en el Foro de la OIA:
http://foro.oia.unsam.edu.arEn particular, en el foro estaran estas charlas subidas a
disposicion de todos.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 103: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/103.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Problemas de Tarea
Problemas (en orden creciente de dificultad (subjetivo))
”Frodo y sus almohadas”http://codeforces.com/problemset/problem/760/B
”Buen kilo de pan flauta”http://www.spoj.com/problems/TAP2015B/
”Anton y el cuento de hadas”http://codeforces.com/problemset/problem/785/C
”Dinosaur menace” (difıcil)http://www.spoj.com/problems/DINOSM/
Siempre pueden hacer consultas sobre problemas (o cualquier temarelacionado con la Olimpıada) en el Foro de la OIA:
http://foro.oia.unsam.edu.arEn particular, en el foro estaran estas charlas subidas a
disposicion de todos.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 104: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/104.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Problemas de Tarea
Problemas (en orden creciente de dificultad (subjetivo))
”Frodo y sus almohadas”http://codeforces.com/problemset/problem/760/B
”Buen kilo de pan flauta”http://www.spoj.com/problems/TAP2015B/
”Anton y el cuento de hadas”http://codeforces.com/problemset/problem/785/C
”Dinosaur menace” (difıcil)http://www.spoj.com/problems/DINOSM/
Siempre pueden hacer consultas sobre problemas (o cualquier temarelacionado con la Olimpıada) en el Foro de la OIA:
http://foro.oia.unsam.edu.arEn particular, en el foro estaran estas charlas subidas a
disposicion de todos.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 105: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/105.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
¡Intervalo! (Recreo)
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 106: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/106.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ventanas Deslizantes
Problema:
Dado un arreglo de n numeros positivos, y un numero x , nosinteresa saber si existe un subarreglo cuya suma sea x .
Ejemplos:
A = [02,
13,
22,
35,
41,
55,
62,
73]. Buscamos sumar x = 8
La respuesta es : ”El subarreglo [2..4] suma 8”
A = [02,
13,
22,
35,
41,
55,
62,
73]. Buscamos sumar x = 4
La respuesta es : ”No hay subarreglo de A que sume 4”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 107: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/107.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ventanas Deslizantes
Problema:
Dado un arreglo de n numeros positivos, y un numero x , nosinteresa saber si existe un subarreglo cuya suma sea x .
Ejemplos:
A = [02,
13,
22,
35,
41,
55,
62,
73]. Buscamos sumar x = 8
La respuesta es : ”El subarreglo [2..4] suma 8”
A = [02,
13,
22,
35,
41,
55,
62,
73]. Buscamos sumar x = 4
La respuesta es : ”No hay subarreglo de A que sume 4”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 108: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/108.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ventanas Deslizantes
Problema:
Dado un arreglo de n numeros positivos, y un numero x , nosinteresa saber si existe un subarreglo cuya suma sea x .
Ejemplos:
A = [02,
13,
22,
35,
41,
55,
62,
73]. Buscamos sumar x = 8
La respuesta es :
”El subarreglo [2..4] suma 8”
A = [02,
13,
22,
35,
41,
55,
62,
73]. Buscamos sumar x = 4
La respuesta es : ”No hay subarreglo de A que sume 4”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 109: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/109.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ventanas Deslizantes
Problema:
Dado un arreglo de n numeros positivos, y un numero x , nosinteresa saber si existe un subarreglo cuya suma sea x .
Ejemplos:
A = [02,
13,
22,
35,
41︸ ︷︷ ︸
2+5+1=8
,55,
62,
73]. Buscamos sumar x = 8
La respuesta es : ”El subarreglo [2..4] suma 8”
A = [02,
13,
22,
35,
41,
55,
62,
73]. Buscamos sumar x = 4
La respuesta es : ”No hay subarreglo de A que sume 4”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 110: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/110.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ventanas Deslizantes
Problema:
Dado un arreglo de n numeros positivos, y un numero x , nosinteresa saber si existe un subarreglo cuya suma sea x .
Ejemplos:
A = [02,
13,
22,
35,
41︸ ︷︷ ︸
2+5+1=8
,55,
62,
73]. Buscamos sumar x = 8
La respuesta es : ”El subarreglo [2..4] suma 8”
A = [02,
13,
22,
35,
41,
55,
62,
73]. Buscamos sumar x = 4
La respuesta es :
”No hay subarreglo de A que sume 4”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 111: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/111.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Ventanas Deslizantes
Problema:
Dado un arreglo de n numeros positivos, y un numero x , nosinteresa saber si existe un subarreglo cuya suma sea x .
Ejemplos:
A = [02,
13,
22,
35,
41︸ ︷︷ ︸
2+5+1=8
,55,
62,
73]. Buscamos sumar x = 8
La respuesta es : ”El subarreglo [2..4] suma 8”
A = [02,
13,
22,
35,
41,
55,
62,
73]. Buscamos sumar x = 4
La respuesta es : ”No hay subarreglo de A que sume 4”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 112: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/112.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Solucion
1 Probar todos los subarreglos posibles. Es decir, todos lossubarreglos [i ..j ] con 0 ≤ j < n e 0 ≤ i ≤ j . Para cada uno deellos calcular suma(i,j), la suma de los numeros en elsubarreglo especificado y ver si es exactamente x .Complejidad : O(n3) u O(n2) dependiendo de laimplementacion de la funcion suma.
2 Utilizar una ventana deslizante para resolver el problema. Laidea es mantener dos ındices que son los extremos de nuestraventana deslizante, al extremo izquierdo lo llamaremos ”i” yal derecho lo llamaremos ”j”. Ambos extremos comienzan enel principio del arreglo, y en todo momento vamos amantener cuanto vale la suma de los numeros dentro dela ventana [i..j) (notar que no incluimos el extremo derecho).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 113: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/113.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Solucion
1 Probar todos los subarreglos posibles. Es decir, todos lossubarreglos [i ..j ] con 0 ≤ j < n e 0 ≤ i ≤ j . Para cada uno deellos calcular suma(i,j), la suma de los numeros en elsubarreglo especificado y ver si es exactamente x .Complejidad :
O(n3) u O(n2) dependiendo de laimplementacion de la funcion suma.
2 Utilizar una ventana deslizante para resolver el problema. Laidea es mantener dos ındices que son los extremos de nuestraventana deslizante, al extremo izquierdo lo llamaremos ”i” yal derecho lo llamaremos ”j”. Ambos extremos comienzan enel principio del arreglo, y en todo momento vamos amantener cuanto vale la suma de los numeros dentro dela ventana [i..j) (notar que no incluimos el extremo derecho).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 114: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/114.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Solucion
1 Probar todos los subarreglos posibles. Es decir, todos lossubarreglos [i ..j ] con 0 ≤ j < n e 0 ≤ i ≤ j . Para cada uno deellos calcular suma(i,j), la suma de los numeros en elsubarreglo especificado y ver si es exactamente x .Complejidad : O(n3) u O(n2) dependiendo de laimplementacion de la funcion suma.
2 Utilizar una ventana deslizante para resolver el problema. Laidea es mantener dos ındices que son los extremos de nuestraventana deslizante, al extremo izquierdo lo llamaremos ”i” yal derecho lo llamaremos ”j”. Ambos extremos comienzan enel principio del arreglo, y en todo momento vamos amantener cuanto vale la suma de los numeros dentro dela ventana [i..j) (notar que no incluimos el extremo derecho).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 115: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/115.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplo Motivador
Solucion
1 Probar todos los subarreglos posibles. Es decir, todos lossubarreglos [i ..j ] con 0 ≤ j < n e 0 ≤ i ≤ j . Para cada uno deellos calcular suma(i,j), la suma de los numeros en elsubarreglo especificado y ver si es exactamente x .Complejidad : O(n3) u O(n2) dependiendo de laimplementacion de la funcion suma.
2 Utilizar una ventana deslizante para resolver el problema. Laidea es mantener dos ındices que son los extremos de nuestraventana deslizante, al extremo izquierdo lo llamaremos ”i” yal derecho lo llamaremos ”j”. Ambos extremos comienzan enel principio del arreglo, y en todo momento vamos amantener cuanto vale la suma de los numeros dentro dela ventana [i..j) (notar que no incluimos el extremo derecho).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 116: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/116.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
2 Utilizar una ventana deslizante para resolver el problema. Laidea es mantener dos ındices que son los extremos de nuestraventana deslizante, al extremo izquierdo lo llamaremos ”i” yal derecho lo llamaremos ”j”. Ambos extremos comienzan enel principio del arreglo, y en todo momento vamos amantener cuanto vale la suma de los numeros dentro dela ventana [i..j) (notar que no incluimos el extremo derecho).
Ejemplo: Si i = 1 y j = 4, mantenemos la suma en el subarreglo
[i ..j) = [1,4) = [1..3].
A = [02,
13,
22,
35,
41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 117: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/117.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
2 Utilizar una ventana deslizante para resolver el problema. Laidea es mantener dos ındices que son los extremos de nuestraventana deslizante, al extremo izquierdo lo llamaremos ”i” yal derecho lo llamaremos ”j”. Ambos extremos comienzan enel principio del arreglo, y en todo momento vamos amantener cuanto vale la suma de los numeros dentro dela ventana [i..j) (notar que no incluimos el extremo derecho).
Ejemplo: Si i = 1 y j = 4, mantenemos la suma en el subarreglo
[i ..j) = [1,4) = [1..3].
A = [02,
13,
22,
35,
41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 118: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/118.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
2 Utilizar una ventana deslizante para resolver el problema. Laidea es mantener dos ındices que son los extremos de nuestraventana deslizante, al extremo izquierdo lo llamaremos ”i” yal derecho lo llamaremos ”j”. Ambos extremos comienzan enel principio del arreglo, y en todo momento vamos amantener cuanto vale la suma de los numeros dentro dela ventana [i..j) (notar que no incluimos el extremo derecho).
Ejemplo: Si i = 1 y j = 4, mantenemos la suma en el subarreglo
[i ..j) = [1,4) = [1..3].
A = [02,
i13,
22,
35︸ ︷︷ ︸
suma=10
,
j41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 119: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/119.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Entrada
Buscamos sumar x = 8
A = [02,
13,
22,
35,
41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 120: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/120.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 1
Buscamos sumar x = 8
suma = 0 < x
→ Aumento j
A = [
i j02,
13,
22,
35,
41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 121: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/121.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 1
Buscamos sumar x = 8
suma = 0 < x → Aumento j
A = [
i j02,
13,
22,
35,
41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 122: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/122.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 2
Buscamos sumar x = 8
suma = 2 < x
→ Aumento j
A = [
i02︸︷︷︸,
j13,
22,
35,
41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 123: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/123.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 2
Buscamos sumar x = 8
suma = 2 < x → Aumento j
A = [
i02︸︷︷︸,
j13,
22,
35,
41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 124: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/124.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 3
Buscamos sumar x = 8
suma = 5 < x
→ Aumento j
A = [
i02,
13︸︷︷︸,
j22,
35,
41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 125: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/125.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 3
Buscamos sumar x = 8
suma = 5 < x → Aumento j
A = [
i02,
13︸︷︷︸,
j22,
35,
41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 126: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/126.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 4
Buscamos sumar x = 8
suma = 7 < x
→ Aumento j
A = [
i02,
13,
22︸ ︷︷ ︸,
j35,
41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 127: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/127.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 4
Buscamos sumar x = 8
suma = 7 < x → Aumento j
A = [
i02,
13,
22︸ ︷︷ ︸,
j35,
41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 128: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/128.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 5
Buscamos sumar x = 8
suma = 12 > x
→ Aumento i
A = [
i02,
13,
22,
35︸ ︷︷ ︸,
j41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 129: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/129.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 5
Buscamos sumar x = 8
suma = 12 > x → Aumento i
A = [
i02,
13,
22,
35︸ ︷︷ ︸,
j41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 130: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/130.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 6
Buscamos sumar x = 8
suma = 10 > x
→ Aumento i
A = [02,
i13,
22,
35︸ ︷︷ ︸,
j41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 131: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/131.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 6
Buscamos sumar x = 8
suma = 10 > x → Aumento i
A = [02,
i13,
22,
35︸ ︷︷ ︸,
j41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 132: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/132.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 7
Buscamos sumar x = 8
suma = 7 < x
→ Aumento j
A = [02,
13,
i22,
35︸︷︷︸,
j41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 133: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/133.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 7
Buscamos sumar x = 8
suma = 7 < x → Aumento j
A = [02,
13,
i22,
35︸︷︷︸,
j41,
55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 134: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/134.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 8
Buscamos sumar x = 8
suma = 8 = x
→ Podemos terminar
A = [02,
13,
i22,
35,
41︸ ︷︷ ︸,
j55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 135: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/135.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Paso 8
Buscamos sumar x = 8
suma = 8 = x → Podemos terminar
A = [02,
13,
i22,
35,
41︸ ︷︷ ︸,
j55,
62,
73]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 136: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/136.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Analisis
¿Cuantos pasos hace el algoritmo?Respuesta : En cada paso, o bien aumenta i o aumenta j.Cada uno de ellos puede ser aumentado a lo sumo n veces.Por lo tanto al cabo de 2n pasos en el peor caso, finalizanuestro algoritmo.
¿Por que es importante que los numeros sean positivos?Respuesta : Porque nos permite saber que si en algunmomento suma > x , entonces todas las ventanas que tienen elmismo valor de i y un j mayor tendran una suma mayor ypodemos no mirarlas (de alguna forma, podemos afirmar que”ya nos pasamos”).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 137: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/137.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Analisis
¿Cuantos pasos hace el algoritmo?Respuesta :
En cada paso, o bien aumenta i o aumenta j.Cada uno de ellos puede ser aumentado a lo sumo n veces.Por lo tanto al cabo de 2n pasos en el peor caso, finalizanuestro algoritmo.
¿Por que es importante que los numeros sean positivos?Respuesta : Porque nos permite saber que si en algunmomento suma > x , entonces todas las ventanas que tienen elmismo valor de i y un j mayor tendran una suma mayor ypodemos no mirarlas (de alguna forma, podemos afirmar que”ya nos pasamos”).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 138: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/138.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Analisis
¿Cuantos pasos hace el algoritmo?Respuesta : En cada paso, o bien aumenta i o aumenta j.Cada uno de ellos puede ser aumentado a lo sumo n veces.Por lo tanto al cabo de 2n pasos en el peor caso, finalizanuestro algoritmo.
¿Por que es importante que los numeros sean positivos?Respuesta : Porque nos permite saber que si en algunmomento suma > x , entonces todas las ventanas que tienen elmismo valor de i y un j mayor tendran una suma mayor ypodemos no mirarlas (de alguna forma, podemos afirmar que”ya nos pasamos”).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 139: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/139.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Analisis
¿Cuantos pasos hace el algoritmo?Respuesta : En cada paso, o bien aumenta i o aumenta j.Cada uno de ellos puede ser aumentado a lo sumo n veces.Por lo tanto al cabo de 2n pasos en el peor caso, finalizanuestro algoritmo.
¿Por que es importante que los numeros sean positivos?Respuesta :
Porque nos permite saber que si en algunmomento suma > x , entonces todas las ventanas que tienen elmismo valor de i y un j mayor tendran una suma mayor ypodemos no mirarlas (de alguna forma, podemos afirmar que”ya nos pasamos”).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 140: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/140.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Analisis
¿Cuantos pasos hace el algoritmo?Respuesta : En cada paso, o bien aumenta i o aumenta j.Cada uno de ellos puede ser aumentado a lo sumo n veces.Por lo tanto al cabo de 2n pasos en el peor caso, finalizanuestro algoritmo.
¿Por que es importante que los numeros sean positivos?Respuesta : Porque nos permite saber que si en algunmomento suma > x , entonces todas las ventanas que tienen elmismo valor de i y un j mayor tendran una suma mayor ypodemos no mirarlas (de alguna forma, podemos afirmar que”ya nos pasamos”).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 141: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/141.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Codigo
// En iR , jR devolvemos la respuesta
void ventanaDeslizante(vector <int > &A, int x, int &iR , int &jR)
{
int n = int(A.size()), j = 0, suma = 0; // La suma en [0,0) es 0
for(int i = 0; i < n; i++) // para cada ventana que empieza en i:
{
// Ingresamos a la ventana hasta pasarnos con la suma desde i
while (j < n && suma < x)
{
suma += A[j];
j++;
}
// Al salir del while: (suma >= x) o (j == n)
if (suma == x)
{
iR = i;
jR = j;
}
// Al avanzar i, sale de la ventana
suma -= A[i];
}
}
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 142: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/142.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ideas y Conceptos
Codigo
// En iR , jR devolvemos la respuesta
void ventanaDeslizante(vector <int > &A, int x, int &iR , int &jR)
{
int n = int(A.size()), j = 0, suma = 0; // La suma en [0,0) es 0
for(int i = 0; i < n; i++) // para cada ventana que empieza en i:
{
// Ingresamos a la ventana hasta pasarnos con la suma desde i
while (j < n && suma < x)
{
suma += A[j];
j++;
}
// Al salir del while: (suma >= x) o (j == n)
if (suma == x)
{
iR = i;
jR = j;
}
// Al avanzar i, sale de la ventana
suma -= A[i];
}
}
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 143: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/143.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
2SUM
Problema:
Dado un arreglo de n numeros, y un numero x . Queremosencontrar dos numeros del arreglo que sumen x , o reportar que noexiste tal par.
Ejemplos:
A = [07,
110,
24,
31,
49,
55,
69,
76]. Buscamos sumar x = 12
La respuesta es : ”Sumando A[0] y A[5] obtenemos 12”
A = [07,
110,
24,
31,
49,
55,
69,
76]. Buscamos sumar x = 4
La respuesta es : ”No hay dos elementos de A que sumen 4”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 144: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/144.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
2SUM
Problema:
Dado un arreglo de n numeros, y un numero x . Queremosencontrar dos numeros del arreglo que sumen x , o reportar que noexiste tal par.
Ejemplos:
A = [07,
110,
24,
31,
49,
55,
69,
76]. Buscamos sumar x = 12
La respuesta es : ”Sumando A[0] y A[5] obtenemos 12”
A = [07,
110,
24,
31,
49,
55,
69,
76]. Buscamos sumar x = 4
La respuesta es : ”No hay dos elementos de A que sumen 4”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 145: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/145.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
2SUM
Problema:
Dado un arreglo de n numeros, y un numero x . Queremosencontrar dos numeros del arreglo que sumen x , o reportar que noexiste tal par.
Ejemplos:
A = [07,
110,
24,
31,
49,
55,
69,
76]. Buscamos sumar x = 12
La respuesta es :
”Sumando A[0] y A[5] obtenemos 12”
A = [07,
110,
24,
31,
49,
55,
69,
76]. Buscamos sumar x = 4
La respuesta es : ”No hay dos elementos de A que sumen 4”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 146: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/146.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
2SUM
Problema:
Dado un arreglo de n numeros, y un numero x . Queremosencontrar dos numeros del arreglo que sumen x , o reportar que noexiste tal par.
Ejemplos:
A = [07,
110,
24,
31,
49,
55,
69,
76]. Buscamos sumar x = 12
La respuesta es : ”Sumando A[0] y A[5] obtenemos 12”
A = [07,
110,
24,
31,
49,
55,
69,
76]. Buscamos sumar x = 4
La respuesta es : ”No hay dos elementos de A que sumen 4”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 147: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/147.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
2SUM
Problema:
Dado un arreglo de n numeros, y un numero x . Queremosencontrar dos numeros del arreglo que sumen x , o reportar que noexiste tal par.
Ejemplos:
A = [07,
110,
24,
31,
49,
55,
69,
76]. Buscamos sumar x = 12
La respuesta es : ”Sumando A[0] y A[5] obtenemos 12”
A = [07,
110,
24,
31,
49,
55,
69,
76]. Buscamos sumar x = 4
La respuesta es :
”No hay dos elementos de A que sumen 4”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 148: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/148.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
2SUM
Problema:
Dado un arreglo de n numeros, y un numero x . Queremosencontrar dos numeros del arreglo que sumen x , o reportar que noexiste tal par.
Ejemplos:
A = [07,
110,
24,
31,
49,
55,
69,
76]. Buscamos sumar x = 12
La respuesta es : ”Sumando A[0] y A[5] obtenemos 12”
A = [07,
110,
24,
31,
49,
55,
69,
76]. Buscamos sumar x = 4
La respuesta es : ”No hay dos elementos de A que sumen 4”
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 149: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/149.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Observacion clave
Es importante notar que el orden de los numeros en el arreglo A nojuega ningun rol. Entonces podemos asumir que tienen el ordenque nos convenga. En particular, podemos asumir que el arregloesta ordenado en forma creciente (u ordenarlo en O(n lg(n)) )
1 Probar todos los pares de ındices, y ver si esos dos numerossuman o no x . De existir un par que sı, reportarlo.Complejidad O(n2)
2 Utilizar una variante de la tecnica que vimos recien pararesolver el problema. En lugar de tener dos ındices quesiempre aumentan, ahora tendremos dos ındices. Unosiempre aumenta, el otro siempre disminuye. Por lo tantotambien haremos a lo sumo 2n pasos. Complejidad O(n).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 150: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/150.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Observacion clave
Es importante notar que el orden de los numeros en el arreglo A nojuega ningun rol. Entonces podemos asumir que tienen el ordenque nos convenga. En particular, podemos asumir que el arregloesta ordenado en forma creciente (u ordenarlo en O(n lg(n)) )
1 Probar todos los pares de ındices, y ver si esos dos numerossuman o no x . De existir un par que sı, reportarlo.Complejidad O(n2)
2 Utilizar una variante de la tecnica que vimos recien pararesolver el problema. En lugar de tener dos ındices quesiempre aumentan, ahora tendremos dos ındices. Unosiempre aumenta, el otro siempre disminuye. Por lo tantotambien haremos a lo sumo 2n pasos. Complejidad O(n).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 151: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/151.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Observacion clave
Es importante notar que el orden de los numeros en el arreglo A nojuega ningun rol. Entonces podemos asumir que tienen el ordenque nos convenga. En particular, podemos asumir que el arregloesta ordenado en forma creciente (u ordenarlo en O(n lg(n)) )
1 Probar todos los pares de ındices, y ver si esos dos numerossuman o no x . De existir un par que sı, reportarlo.Complejidad O(n2)
2 Utilizar una variante de la tecnica que vimos recien pararesolver el problema. En lugar de tener dos ındices quesiempre aumentan, ahora tendremos dos ındices. Unosiempre aumenta, el otro siempre disminuye. Por lo tantotambien haremos a lo sumo 2n pasos. Complejidad O(n).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 152: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/152.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
Observacion clave
Es importante notar que el orden de los numeros en el arreglo A nojuega ningun rol. Entonces podemos asumir que tienen el ordenque nos convenga. En particular, podemos asumir que el arregloesta ordenado en forma creciente (u ordenarlo en O(n lg(n)) )
1 Probar todos los pares de ındices, y ver si esos dos numerossuman o no x . De existir un par que sı, reportarlo.Complejidad O(n2)
2 Utilizar una variante de la tecnica que vimos recien pararesolver el problema. En lugar de tener dos ındices quesiempre aumentan, ahora tendremos dos ındices. Unosiempre aumenta, el otro siempre disminuye. Por lo tantotambien haremos a lo sumo 2n pasos. Complejidad O(n).
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 153: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/153.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Entrada
Buscamos sumar x = 12
A = [01,
14,
25,
36,
47,
59,
69,
710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 154: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/154.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Paso 1
Buscamos sumar x = 12
11︷ ︸︸ ︷A[i ] + A[j ] < x
→ Aumento i
A = [
i01,
14,
25,
36,
47,
59,
69,
j710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 155: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/155.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Paso 1
Buscamos sumar x = 12
11︷ ︸︸ ︷A[i ] + A[j ] < x → Aumento i
A = [
i01,
14,
25,
36,
47,
59,
69,
j710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 156: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/156.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Paso 2
Buscamos sumar x = 12
14︷ ︸︸ ︷A[i ] + A[j ] > x
→ Disminuyo j
A = [01,
i14,
25,
36,
47,
59,
69,
j710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 157: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/157.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Paso 2
Buscamos sumar x = 12
14︷ ︸︸ ︷A[i ] + A[j ] > x → Disminuyo j
A = [01,
i14,
25,
36,
47,
59,
69,
j710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 158: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/158.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Paso 3
Buscamos sumar x = 12
13︷ ︸︸ ︷A[i ] + A[j ] > x
→ Disminuyo j
A = [01,
i14,
25,
36,
47,
59,
j69,
710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 159: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/159.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Paso 3
Buscamos sumar x = 12
13︷ ︸︸ ︷A[i ] + A[j ] > x → Disminuyo j
A = [01,
i14,
25,
36,
47,
59,
j69,
710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 160: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/160.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Paso 4
Buscamos sumar x = 12
13︷ ︸︸ ︷A[i ] + A[j ] > x
→ Disminuyo j
A = [01,
i14,
25,
36,
47,
j59,
69,
710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 161: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/161.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Paso 4
Buscamos sumar x = 12
13︷ ︸︸ ︷A[i ] + A[j ] > x → Disminuyo j
A = [01,
i14,
25,
36,
47,
j59,
69,
710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 162: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/162.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Paso 5
Buscamos sumar x = 12
11︷ ︸︸ ︷A[i ] + A[j ] < x
→ Aumento i
A = [01,
i14,
25,
36,
j47,
59,
69,
710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 163: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/163.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Paso 5
Buscamos sumar x = 12
11︷ ︸︸ ︷A[i ] + A[j ] < x → Aumento i
A = [01,
i14,
25,
36,
j47,
59,
69,
710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 164: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/164.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Paso 6
Buscamos sumar x = 12
12︷ ︸︸ ︷A[i ] + A[j ] = x
→ Podemos terminar
A = [01,
14,
i25,
36,
j47,
59,
69,
710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 165: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/165.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Paso 6
Buscamos sumar x = 12
12︷ ︸︸ ︷A[i ] + A[j ] = x → Podemos terminar
A = [01,
14,
i25,
36,
j47,
59,
69,
710]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 166: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/166.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Codigo
// En iR, jR devolvemos la respuesta
void ventanaDeslizante(vector <int > &A, int x, int &iR,
{ int &jR)
int n = int(A.size()), j = n-1;
for(int i = 0; i < n; i++) // fijando el extremo i:
{ // mientras la suma sea > x, disminuimos j
while (j > i && A[i] + A[j] > x)
j--;
// Sale del while : (A[i] + A[j] <= x) o (j == i)
if (j > i && A[i] + A[j] == x)
{
iR = i;
jR = j;
}
}
}
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 167: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/167.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Codigo
// En iR, jR devolvemos la respuesta
void ventanaDeslizante(vector <int > &A, int x, int &iR,
{ int &jR)
int n = int(A.size()), j = n-1;
for(int i = 0; i < n; i++) // fijando el extremo i:
{ // mientras la suma sea > x, disminuimos j
while (j > i && A[i] + A[j] > x)
j--;
// Sale del while : (A[i] + A[j] <= x) o (j == i)
if (j > i && A[i] + A[j] == x)
{
iR = i;
jR = j;
}
}
}
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 168: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/168.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Problema:
Dados n puntos en la recta numerica (x1, x2, . . . , xn), y un numerok . Si listamos todas las distancias entre pares de puntos (xi , xj)con i < j y ordenamos estas distancias (puede haber repetidas).Queremos saber que distancia queda en el k-esimo lugar.
1 dist(x1, x2) = 8
2 dist(x1, x3) = 3
3 dist(x1, x4) = 4
4 dist(x2, x3) = 11
5 dist(x2, x4) = 4
6 dist(x3, x4) = 7
D = [13,
24,
34,
47,
58,
611]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 169: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/169.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Problema:
Dados n puntos en la recta numerica (x1, x2, . . . , xn), y un numerok . Si listamos todas las distancias entre pares de puntos (xi , xj)con i < j y ordenamos estas distancias (puede haber repetidas).Queremos saber que distancia queda en el k-esimo lugar.
1 dist(x1, x2) = 8
2 dist(x1, x3) = 3
3 dist(x1, x4) = 4
4 dist(x2, x3) = 11
5 dist(x2, x4) = 4
6 dist(x3, x4) = 7
D = [13,
24,
34,
47,
58,
611]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 170: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/170.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Problema:
Dados n puntos en la recta numerica (x1, x2, . . . , xn), y un numerok . Si listamos todas las distancias entre pares de puntos (xi , xj)con i < j y ordenamos estas distancias (puede haber repetidas).Queremos saber que distancia queda en el k-esimo lugar.
1 dist(x1, x2) = 8
2 dist(x1, x3) = 3
3 dist(x1, x4) = 4
4 dist(x2, x3) = 11
5 dist(x2, x4) = 4
6 dist(x3, x4) = 7
D = [13,
24,
34,
47,
58,
611]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 171: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/171.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Problema:
Dados n puntos en la recta numerica (x1, x2, . . . , xn), y un numerok . Si listamos todas las distancias entre pares de puntos (xi , xj)con i < j y ordenamos estas distancias (puede haber repetidas).Queremos saber que distancia queda en el k-esimo lugar.
1 dist(x1, x2) = 8
2 dist(x1, x3) = 3
3 dist(x1, x4) = 4
4 dist(x2, x3) = 11
5 dist(x2, x4) = 4
6 dist(x3, x4) = 7
D = [13,
24,
34,
47,
58,
611]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 172: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/172.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Problema:
Dados n puntos en la recta numerica (x1, x2, . . . , xn), y un numerok . Si listamos todas las distancias entre pares de puntos (xi , xj)con i < j y ordenamos estas distancias (puede haber repetidas).Queremos saber que distancia queda en el k-esimo lugar.
1 dist(x1, x2) = 8
2 dist(x1, x3) = 3
3 dist(x1, x4) = 4
4 dist(x2, x3) = 11
5 dist(x2, x4) = 4
6 dist(x3, x4) = 7
D = [13,
24,
34,
47,
58,
611]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 173: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/173.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Problema:
Dados n puntos en la recta numerica (x1, x2, . . . , xn), y un numerok . Si listamos todas las distancias entre pares de puntos (xi , xj)con i < j y ordenamos estas distancias (puede haber repetidas).Queremos saber que distancia queda en el k-esimo lugar.
1 dist(x1, x2) = 8
2 dist(x1, x3) = 3
3 dist(x1, x4) = 4
4 dist(x2, x3) = 11
5 dist(x2, x4) = 4
6 dist(x3, x4) = 7
D = [13,
24,
34,
47,
58,
611]
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 174: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/174.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
1 Calcular todas las distancias, ordenarlas, y ver que elementoesta en el k-esimo lugar. Complejidad : O(n2 + n2 lg(n2))
2 Usar Binary Search y una Ventana deslizante. Haremosbusqueda binaria en la distancia. Formalmente, la propiedadsera :P(d) : La cantidad de distancias menores que d es menor que k
Ordenados los puntos, para una distancia d fija, podemos ir
moviendo una ventana deslizante que para cada extremoizquierdo nos diga cuantos puntos estan a distanciamenor que d .Complejidad : O(n lg(n)︸ ︷︷ ︸
Ordenar
+ lg(n)︸︷︷︸BB
· n︸︷︷︸VD
) = O(n lg(n))
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 175: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/175.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
1 Calcular todas las distancias, ordenarlas, y ver que elementoesta en el k-esimo lugar. Complejidad : O(n2 + n2 lg(n2))
2 Usar Binary Search y una Ventana deslizante. Haremosbusqueda binaria en la distancia. Formalmente, la propiedadsera :P(d) : La cantidad de distancias menores que d es menor que k
Ordenados los puntos, para una distancia d fija, podemos ir
moviendo una ventana deslizante que para cada extremoizquierdo nos diga cuantos puntos estan a distanciamenor que d .Complejidad : O(n lg(n)︸ ︷︷ ︸
Ordenar
+ lg(n)︸︷︷︸BB
· n︸︷︷︸VD
) = O(n lg(n))
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 176: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/176.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
1 Calcular todas las distancias, ordenarlas, y ver que elementoesta en el k-esimo lugar. Complejidad : O(n2 + n2 lg(n2))
2 Usar Binary Search y una Ventana deslizante.
Haremosbusqueda binaria en la distancia. Formalmente, la propiedadsera :P(d) : La cantidad de distancias menores que d es menor que k
Ordenados los puntos, para una distancia d fija, podemos ir
moviendo una ventana deslizante que para cada extremoizquierdo nos diga cuantos puntos estan a distanciamenor que d .Complejidad : O(n lg(n)︸ ︷︷ ︸
Ordenar
+ lg(n)︸︷︷︸BB
· n︸︷︷︸VD
) = O(n lg(n))
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 177: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/177.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
1 Calcular todas las distancias, ordenarlas, y ver que elementoesta en el k-esimo lugar. Complejidad : O(n2 + n2 lg(n2))
2 Usar Binary Search y una Ventana deslizante. Haremosbusqueda binaria en la distancia. Formalmente, la propiedadsera :P(d) : La cantidad de distancias menores que d es menor que k
Ordenados los puntos, para una distancia d fija, podemos ir
moviendo una ventana deslizante que para cada extremoizquierdo nos diga cuantos puntos estan a distanciamenor que d .Complejidad : O(n lg(n)︸ ︷︷ ︸
Ordenar
+ lg(n)︸︷︷︸BB
· n︸︷︷︸VD
) = O(n lg(n))
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 178: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/178.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
1 Calcular todas las distancias, ordenarlas, y ver que elementoesta en el k-esimo lugar. Complejidad : O(n2 + n2 lg(n2))
2 Usar Binary Search y una Ventana deslizante. Haremosbusqueda binaria en la distancia. Formalmente, la propiedadsera :P(d) : La cantidad de distancias menores que d es menor que k
Ordenados los puntos, para una distancia d fija, podemos ir
moviendo una ventana deslizante que para cada extremoizquierdo nos diga cuantos puntos estan a distanciamenor que d .
Complejidad : O(n lg(n)︸ ︷︷ ︸Ordenar
+ lg(n)︸︷︷︸BB
· n︸︷︷︸VD
) = O(n lg(n))
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 179: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/179.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Ejemplos
Solucion
1 Calcular todas las distancias, ordenarlas, y ver que elementoesta en el k-esimo lugar. Complejidad : O(n2 + n2 lg(n2))
2 Usar Binary Search y una Ventana deslizante. Haremosbusqueda binaria en la distancia. Formalmente, la propiedadsera :P(d) : La cantidad de distancias menores que d es menor que k
Ordenados los puntos, para una distancia d fija, podemos ir
moviendo una ventana deslizante que para cada extremoizquierdo nos diga cuantos puntos estan a distanciamenor que d .Complejidad : O(n lg(n)︸ ︷︷ ︸
Ordenar
+ lg(n)︸︷︷︸BB
· n︸︷︷︸VD
) = O(n lg(n))
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 180: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/180.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Problemas de Tarea
Problemas (en orden creciente de dificultad (subjetivo))
”Dıas feriados”http://juez.oia.unsam.edu.ar/#/task/feriados/statement
”Fila”http://juez.oia.unsam.edu.ar/#/task/fila/statement
”Trip Compulsion” (difıcil)http://coj.uci.cu/24h/problem.xhtml?pid=3882
”Distancias extranas” (difıcil)https://csacademy.com/contest/archive/task/strange-distance
Siempre pueden hacer consultas sobre problemas (o cualquier temarelacionado con la Olimpıada) en el Foro de la OIA:
http://foro.oia.unsam.edu.arEn particular, en el foro estaran estas charlas subidas a
disposicion de todos.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 181: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/181.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Problemas de Tarea
Problemas (en orden creciente de dificultad (subjetivo))
”Dıas feriados”http://juez.oia.unsam.edu.ar/#/task/feriados/statement
”Fila”http://juez.oia.unsam.edu.ar/#/task/fila/statement
”Trip Compulsion” (difıcil)http://coj.uci.cu/24h/problem.xhtml?pid=3882
”Distancias extranas” (difıcil)https://csacademy.com/contest/archive/task/strange-distance
Siempre pueden hacer consultas sobre problemas (o cualquier temarelacionado con la Olimpıada) en el Foro de la OIA:
http://foro.oia.unsam.edu.arEn particular, en el foro estaran estas charlas subidas a
disposicion de todos.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes
![Page 182: Busqueda Binaria y Ventanas Deslizantes - … · Dado un arreglo ordenado de n numeros (A), queremos saber si el elemento x se encuentra en el. En caso de encontrarse, buscamos la](https://reader031.vdocumento.com/reader031/viewer/2022021612/5ba1383909d3f2c06a8bdd12/html5/thumbnails/182.jpg)
Busqueda Binaria Intervalo Ventanas Deslizantes
Problemas de Tarea
Problemas (en orden creciente de dificultad (subjetivo))
”Dıas feriados”http://juez.oia.unsam.edu.ar/#/task/feriados/statement
”Fila”http://juez.oia.unsam.edu.ar/#/task/fila/statement
”Trip Compulsion” (difıcil)http://coj.uci.cu/24h/problem.xhtml?pid=3882
”Distancias extranas” (difıcil)https://csacademy.com/contest/archive/task/strange-distance
Siempre pueden hacer consultas sobre problemas (o cualquier temarelacionado con la Olimpıada) en el Foro de la OIA:
http://foro.oia.unsam.edu.arEn particular, en el foro estaran estas charlas subidas a
disposicion de todos.
Facundo Gutierrez
Busqueda Binaria y Ventanas Deslizantes