Post on 09-Oct-2015
transcript
Busqueda Binaria y Ternaria
Matias Tealdi1
1Facultad de Matemtica, Astronoma y FsicaUniversidad Nacional de Crdoba
Training Camp 2012
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 1 / 36
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 2 / 36
Bsqueda Binaria Discreta. Qu es y para qu sirve? Ejemplo.
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 3 / 36
Bsqueda Binaria Discreta. Qu es y para qu sirve? Ejemplo.
Qu es y para qu sirve? Ejemplo.
Dada una lista ordenada de primos menores a 55, decidir si unnmero r menor a 55 es primo.
arr = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}assert(arr.size() == 16)
Bsqueda Lineal.Recorremos elemento por elemento y chequeamos si r
esta en la lista.Complejidad : O(n)
Bsqueda Binaria.Tomamos el intervalo [a..b] nos fijamos si el elemento
[(a+ b)/2] es menor igual a r . Si lo es, solo me trengo que fijar sir esta en [a, (a+ b)/2], sino r tiene q estar en [(a+ b)/2,b]. Aplicorecursivamente la misma idea.
Complejidad : O(log n)
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 4 / 36
Bsqueda Binaria Discreta. Qu es y para qu sirve? Ejemplo.
Qu es y para qu sirve? Ejemplo.
Dada una lista ordenada de primos menores a 55, decidir si unnmero r menor a 55 es primo.arr = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}assert(arr.size() == 16)
Bsqueda Lineal.Recorremos elemento por elemento y chequeamos si r
esta en la lista.Complejidad : O(n)
Bsqueda Binaria.Tomamos el intervalo [a..b] nos fijamos si el elemento
[(a+ b)/2] es menor igual a r . Si lo es, solo me trengo que fijar sir esta en [a, (a+ b)/2], sino r tiene q estar en [(a+ b)/2,b]. Aplicorecursivamente la misma idea.
Complejidad : O(log n)
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 4 / 36
Bsqueda Binaria Discreta. Qu es y para qu sirve? Ejemplo.
Qu es y para qu sirve? Ejemplo.
Dada una lista ordenada de primos menores a 55, decidir si unnmero r menor a 55 es primo.arr = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}assert(arr.size() == 16)
Bsqueda Lineal.Recorremos elemento por elemento y chequeamos si r
esta en la lista.Complejidad : O(n)
Bsqueda Binaria.Tomamos el intervalo [a..b] nos fijamos si el elemento
[(a+ b)/2] es menor igual a r . Si lo es, solo me trengo que fijar sir esta en [a, (a+ b)/2], sino r tiene q estar en [(a+ b)/2,b]. Aplicorecursivamente la misma idea.
Complejidad : O(log n)
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 4 / 36
Bsqueda Binaria Discreta. Qu es y para qu sirve? Ejemplo.
Qu es y para qu sirve? Ejemplo.
Dada una lista ordenada de primos menores a 55, decidir si unnmero r menor a 55 es primo.arr = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}assert(arr.size() == 16)
Bsqueda Lineal.Recorremos elemento por elemento y chequeamos si r
esta en la lista.Complejidad : O(n)
Bsqueda Binaria.Tomamos el intervalo [a..b] nos fijamos si el elemento
[(a+ b)/2] es menor igual a r . Si lo es, solo me trengo que fijar sir esta en [a, (a+ b)/2], sino r tiene q estar en [(a+ b)/2,b]. Aplicorecursivamente la misma idea.
Complejidad : O(log n)
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 4 / 36
Bsqueda Binaria Discreta. Implementacin.
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 5 / 36
Bsqueda Binaria Discreta. Implementacin.
Implementacin de Bsqueda Binaria Discreta
1 int bsearch(const vector &arr , int r ) {2 int l e f t = 0, right = n;3 while ( rightleft >1) {4 int mid = ( lef t+right ) /2;5 i f ( arr [mid]
Bsqueda Binaria Discreta. Generalizacin
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 7 / 36
Bsqueda Binaria Discreta. Generalizacin
Generalizacin
Dado un intervalo [a, b], y una propiedad P sobre el intervalo talque x , y en [a,b], si x < y entonces P(y) = P(x), BS nosencuentra el elemento ms grande que cumple P o el elementoms chico que no cumple P (el siguiente del ms grande quecumple P).
Demostracin Informal utilizando induccin.Supongamos que tenemos un intervalo [a,b] tal que cumple lascondiciones dadas arriba. Adems supongamos que hay almenos un elemento en [a,b] que cumple P.
Si [a,b] tiene un elemnto, entonces ya tengo el elemento msgrande que cumple P.
Si [a,b] tiene tamao n>1. Sea mid = (a+ b)/2, si P(mid) vale,entoces como P es monotona estoy seguro que el elemento msgrande que vale P esta en [mid, b] de lo contrario estoy seguro deque esta en [a, mid].
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 8 / 36
Bsqueda Binaria Discreta. Generalizacin
Generalizacin
Dado un intervalo [a, b], y una propiedad P sobre el intervalo talque x , y en [a,b], si x < y entonces P(y) = P(x), BS nosencuentra el elemento ms grande que cumple P o el elementoms chico que no cumple P (el siguiente del ms grande quecumple P).Demostracin Informal utilizando induccin.Supongamos que tenemos un intervalo [a,b] tal que cumple lascondiciones dadas arriba. Adems supongamos que hay almenos un elemento en [a,b] que cumple P.
Si [a,b] tiene un elemnto, entonces ya tengo el elemento msgrande que cumple P.
Si [a,b] tiene tamao n>1. Sea mid = (a+ b)/2, si P(mid) vale,entoces como P es monotona estoy seguro que el elemento msgrande que vale P esta en [mid, b] de lo contrario estoy seguro deque esta en [a, mid].
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 8 / 36
Bsqueda Binaria Discreta. Generalizacin
Generalizacin
Dado un intervalo [a, b], y una propiedad P sobre el intervalo talque x , y en [a,b], si x < y entonces P(y) = P(x), BS nosencuentra el elemento ms grande que cumple P o el elementoms chico que no cumple P (el siguiente del ms grande quecumple P).Demostracin Informal utilizando induccin.Supongamos que tenemos un intervalo [a,b] tal que cumple lascondiciones dadas arriba. Adems supongamos que hay almenos un elemento en [a,b] que cumple P.
Si [a,b] tiene un elemnto, entonces ya tengo el elemento msgrande que cumple P.
Si [a,b] tiene tamao n>1. Sea mid = (a+ b)/2, si P(mid) vale,entoces como P es monotona estoy seguro que el elemento msgrande que vale P esta en [mid, b] de lo contrario estoy seguro deque esta en [a, mid].
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 8 / 36
Bsqueda Binaria Discreta. Generalizacin
Generalizacin
Dado un intervalo [a, b], y una propiedad P sobre el intervalo talque x , y en [a,b], si x < y entonces P(y) = P(x), BS nosencuentra el elemento ms grande que cumple P o el elementoms chico que no cumple P (el siguiente del ms grande quecumple P).Demostracin Informal utilizando induccin.Supongamos que tenemos un intervalo [a,b] tal que cumple lascondiciones dadas arriba. Adems supongamos que hay almenos un elemento en [a,b] que cumple P.
Si [a,b] tiene un elemnto, entonces ya tengo el elemento msgrande que cumple P.
Si [a,b] tiene tamao n>1. Sea mid = (a+ b)/2, si P(mid) vale,entoces como P es monotona estoy seguro que el elemento msgrande que vale P esta en [mid, b] de lo contrario estoy seguro deque esta en [a, mid].Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 8 / 36
Bsqueda Binaria Discreta. Anlisis de Complejidad
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 9 / 36
Bsqueda Binaria Discreta. Anlisis de Complejidad
Anlisis de Complejidad
Sea n = h-l el tamao del intervalo. complejidad de hacer bsquedabinaria en [a,b] es log2(n).
Si corremos el algoritmo veremos que en cada paso el tamao delintervalo se divide en 2.n , n/2 , n/4, n/8 ... hasta llegar a 1
La cantidad de veces que se ejecuta el ciclo es log2(n)
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 10 / 36
Bsqueda Binaria Discreta. Implementacin de Generalizacin
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 11 / 36
Bsqueda Binaria Discreta. Implementacin de Generalizacin
Implementacin de Bsqueda Binaria Discreta
1 int bsearch( . . . ) {2 int l e f t = 0, right = n;3 while ( rightleft >1) {4 int mid = ( right+lef t ) /2;5 i f (P(mid) ) {6 l e f t = mid;7 } else {8 right = mid;9 }
10 }11 return l e f t ;12 }
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 12 / 36
Bsqueda Binaria Discreta. Implementacin de Generalizacin
Implementacin recursiva de Bsqueda BinariaDiscreta
1 int bsearch_rec( int left , int right , . . . ) {2 i f ( rightl e f t
Bsqueda Binaria Discreta. Implementacin de Generalizacin
Ejemplos
n input, decir si n es primo menor igual a 55.BS usando P(x) : x
Bsqueda Binaria Discreta. Implementacin de Generalizacin
Ejemplos
n input, decir si n es primo menor igual a 55.BS usando P(x) : x
Bsqueda Binaria Discreta. Implementacin de Generalizacin
Ejemplos
n input, decir si n es primo menor igual a 55.BS usando P(x) : x
Bsqueda Binaria Discreta. Implementacin de Generalizacin
Ejemplos
Dado n cajas tal que en cada caja entran c[i] elementos. Dados relementos, distribuir los r elementos tal que la cantidad deelementos en la caja que ms tiene sea mnimo. Devolver estevalor.
P(x) = puedo poner los r elementos de tal modo que cada caja notiene ms de x elementos.
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 15 / 36
Bsqueda Binaria Discreta. Implementacin de Generalizacin
Ejemplos
Dado n cajas tal que en cada caja entran c[i] elementos. Dados relementos, distribuir los r elementos tal que la cantidad deelementos en la caja que ms tiene sea mnimo. Devolver estevalor.
P(x) = puedo poner los r elementos de tal modo que cada caja notiene ms de x elementos.
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 15 / 36
Bsqueda Binaria Discreta. Implementacin de Generalizacin
Implementacin
1
2 assert ( r > 0 && sum_i(c[ i ]) >= r ) ;3 int l e f t = 0, right = r ;4 while( left
Bsqueda Binaria Real Generalizacin
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 17 / 36
Bsqueda Binaria Real Generalizacin
Generalizacin
Dadas una funcin f continua creciente o decreciente, en unintervalo [a,b]Es decir,creciente, si para todo x y = f (x) f (y) o,decreciente, si para todo x y = f (y) f (x)
Dado y, supongamos que existe x en [a,b] tal que f (x) = y ,BS sirve para encontrar el valor de x tal que f (x) = y
Puede haber error de precisin de punto flotante.
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 18 / 36
Bsqueda Binaria Real Generalizacin
Generalizacin
Dadas una funcin f continua creciente o decreciente, en unintervalo [a,b]Es decir,creciente, si para todo x y = f (x) f (y) o,decreciente, si para todo x y = f (y) f (x)
Dado y, supongamos que existe x en [a,b] tal que f (x) = y ,BS sirve para encontrar el valor de x tal que f (x) = yPuede haber error de precisin de punto flotante.
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 18 / 36
Bsqueda Binaria Real Cdigo
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 19 / 36
Bsqueda Binaria Real Cdigo
Cdigo
1 double l e f t = a , right = b;2 while( rightl e f t > EPS) {3 double mid = ( lef t+right ) /2;4 i f ( f (mid) < y) le f t = mid;5 else right = mid;6 }7 return ( le f t+right ) /2;
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 20 / 36
Bsqueda Binaria Real Cdigo
Cdigo
1 double l e f t = a , right = b;2 /x entre 30 y 100, aprox log(hl ) + 30 si el EPS es 10E9/3 for ( t=0 ; t
Bsqueda Binaria Real Algunas custiones sobre nmeros reales
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 22 / 36
Bsqueda Binaria Real Algunas custiones sobre nmeros reales
Algunas custiones sobre nmeros reales
Como los nmeros reales son infinitos, esta claro que la computadorano los puede representar a todos. Por ello, las operaciones con puntoflotante pueden tener errores de precisin.
Para solucionar este inconveniente, muchas veces se utiliza valoresconstantes muy pequeos a los que llamamos epsilon. Este valor nospermite darle un margen al error.
Por ejemplo : Supongamos x, y dos nmeros double y EPS = 10E-9x < y, deberiamos hacer x < y-EPSx == y, deberiamos hacer fabs(x-y) < EPSEl resto de las operaciones las podemos armar en funcin de estasdos.
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 23 / 36
Bsqueda Binaria Real Algunas custiones sobre nmeros reales
Problemas que puede haber con manejo de nmerosreales.
Por ejemplo, en la BS, es posible que ((a+b)/2 == a) e incluso que(a/2+b/2) < a. En este caso, si utilizamos un EPS muy pequeo,puede ocurrir que nunca se haga falsa la codicin del while.Que (a1 + a2) + a3 ! = a1 + (a2 + a3)Que (a1 + a2)/2 ! = a1/2 + a2/2
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 24 / 36
Bsqueda Binaria Real Algunas custiones sobre nmeros reales
Ejemplos
Encontrar la raz cuadrada de r.Si bien la bsqueda binaria no es el mtodo ms preciso deencontrar la raz cuadrada de un nmero, sirve de ejemplo eneste caso.
Sabemos que la funcin de raz cuadrada es una funcinmonotona creciente, por lo tanto solo tenemos que aplicar elalgoritmo de BS con el predicado P(x) = x x < r .
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 25 / 36
Bsqueda Ternaria Concepto
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 26 / 36
Bsqueda Ternaria Concepto
Concepto
Es una tcnica para encontrar el mximo o mnimo en unintervalo de un funcin que es estrictamente creciente en unintervalo y luego estrictamente decreciente o viceversa.Se puede aplicar en funciones continuas o discretas.En funciones discretas es importante verificar que la funcincumpla que sea estrictamente creciente y luego estrictamentedecreciente. (no dos valores consecutivos iguales).
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 27 / 36
Bsqueda Ternaria Generalizacin
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 28 / 36
Bsqueda Ternaria Generalizacin
Generalizacin
Asumamos que estamos buscando el mximo de una funcin f , ysabemos que el mximo esta en el intervalo [A,B]. Para poderaplicar TS, debe existir algn valor x tal que
a,b con A
Bsqueda Ternaria Algoritmo
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 30 / 36
Bsqueda Ternaria Algoritmo
Algoritmo
1 double TS(double A, double B) {2 double l e f t = A, right = B;3 while(abs( rightl e f t ) < EPS) {4 double l t = (2. l e f t + right ) / 3;5 double r t = ( le f t + 2. right ) / 3;6 i f ( f ( l t ) < f ( r t ) ) le f t = l t ;7 else right = r t ;8 }9 return ( le f t+right ) /2;
10 }
Tiene el mismo problema de precisin que la BS continua, sesoluciona del mismo modo.
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 31 / 36
Bsqueda Ternaria Complejidad
Contenidos
1 Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
2 Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
3 Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 32 / 36
Bsqueda Ternaria Complejidad
Complejidad
En cada paso del ciclo dividimos el intervalo en 3 y achicamos elnuevo intervalo a 2/3 del intervalo inicial.Por lo tanto generamos una secuencia de intervalos de la forma
n, (2/3) n, (4/9) n, ..(2j/3j) n
Buscamos que el (2/3)j sea tan chico como EPS/n
Por lo tanto la coplejidad de BT es O(log2/3(n)) = O(log(n))
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 33 / 36
Bsqueda Ternaria Complejidad
Ejemplos
Supongamos que granjero John viven en una casa en laposicin (xh, yh) con yh>0, y quiere regar su rbol que est en laposicin (xa,ya), con ya>0. Para poder regarlo, John camina hasta elro que se encuentra en el eje x, toma agua y se dirige hasta el rbol.
Cual es la minma distancia que tiene que recorrer granjeroJohn para regar su rbol.
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 34 / 36
Bsqueda Ternaria Complejidad
Algoritmo
1 #define EPS 1E92 int main () {3 double xh, yh, xa , ya;4 cin >> xh >> yh;5 cin >> xa >> ya;6 i f (xh < xa) swap(xh, xa) , swap(yh, ya) ;7
8 double l e f t = xh, right = xa;9 while( fabs( rightl e f t ) > EPS) {
10 double pl = (2 l e f t + right ) / 3. ;11 double pr = ( le f t + 2right ) / 3. ;12 i f ( f (pl , xh, yh, xa , ya) < f (pr , xh, yh, xa , ya)EPS)13 right = pr ;14 else l e f t = pl ;15 }16 cout
Bsqueda Ternaria Complejidad
Algoritmo
1 #define sqr (A) ((A)(A) )2 double f (double x, double xh, double yh, double xa, double ya) {3 return sqrt ( sqr (xhx) + sqr (yh) ) + sqrt ( sqr (xax) + sqr (ya) ) ;4 }
Matias Tealdi (UNC) Busqueda Binaria y Ternaria TC 2012 36 / 36
Bsqueda Binaria Discreta.Qu es y para qu sirve? Ejemplo.Implementacin.GeneralizacinAnlisis de ComplejidadImplementacin de Generalizacin
Bsqueda Binaria RealGeneralizacinCdigoAlgunas custiones sobre nmeros reales
Bsqueda TernariaConceptoGeneralizacinAlgoritmoComplejidad