Upper bound en java

La funcion en c++ de upper_bound suele ser muy util. En java quedaria algo como lo que aparece en la siguiente imagen:

Asi tendriamos complejidad de O(log2(n))

Basicamente se trata de escribir una busqueda binaria y modificarla.

El if final es por si no encontramos ningun valor mayor que el dado, entonces al igual que en la funcion de C++ se devuelve la posicion final dada a la funcion.

Búsqueda binaria

Hola, en muchas ocasiones tendremos que escribir una búsqueda binaria y deberemos tener el concepto claro, ya que no siempre se puede ver tan fácilmente que el problema que debemos solucionar, se puede resolver con una búsqueda binaria.

Primero que todo hay que aclarar, la búsqueda binaria, nos sirve para eso, buscar. Segundo, la restricción para usar la búsqueda binaria es que los elementos estén ordenados. Tercero, si queremos obtener un beneficio de esta, debe realizarse sobre una estructura a la cual se pueda acceder a cualquier elemento en tiempo constante, es decir O(1).

La idea del algoritmo está basado en el paradigma divide y vencerás. Divide y vencerás viene de los romanos, ya no recuerdo por qué, pero lo importante es la idea detrás. Se suele hablar de dividir un problema en subproblemas y de esta forma resolverlos más fácilmente. En la búsqueda binaria se aplica simplemente dividiendo el arreglo en dos, olvidando lo que no nos interesa y centrándonos en lo que sí.

Si tenemos un arreglo y sabemos que está ordenado, por ejemplo:

1 3 6 8 9 11 15

y necesitamos buscar el número 9 y hacemos una búsqueda lineal(iterar uno por uno) tendríamos que hacer 6 iteraciones. Sin embargo, si nos damos cuenta, no es necesario iterar por cada uno y verificar que sea el número que buscamos, por ejemplo, si estamos en la mitad(número 8) sabremos que si el valor que buscamos está en el arreglo tendría que estar a la derecha, y no es necesario buscarlo en la mitad de la izquierda. De esta forma ya nos habremos olvidado de la mitad del arreglo. Luego, podríamos, ¿por qué no?, hacer lo mismo con el arreglo resultante y verificar si el número está en este arreglo, ¿cómo? mirando si es el valor de la mitad el que buscamos. Se recomienda que se haga por cuenta propia el intento de escribir el código que realiza esto, lo cual no es muy complicado. A continuación el pseudocódigo:

Por la ley de la tricotomía, para los enteros se cumple que solo puede entrar a un if de los mostrados anteriormente, y como de una u otra forma, en los computadores sólo trabajamos con valores enteros, entonces podemos estar tranquilos.

Escribir esto en código no es muy complicado, solo hay que tener cuidado de no enredarse, ya sea por desesperación o apuro se pueden cometer errores tontos :)

Finalmente, al dividir el arreglo en dos cada vez, estamos obteniendo una complejidad de O(log(n)) lo cual es lo suficientemente rápido para valores muy grandes. Digamos 10**1000 tiene 1000 dígitos y aún así podríamos buscar un valor en 3321 iteraciones, lo cual no es nada comparado con la cantidad de elementos en total.

Si no tenemos los elementos ordenados, tendremos que pensarlo dos veces, ya que la forma más rápida de ordenar es lineal, es decir O(n), pero con ciertas restricciones y para propósito general tenemos O(n*log(n))

En el siguiente link pueden encontrar implementaciones en varios lenguajes de programación:  http://www.codecodex.com/wiki/Binary_search

Información adicional:
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch

Criba de Eratostenes

Hola, antes habia puesto un par de algoritmos para saber si un numero era primo, pero y si queremos saber la cantidad de primos en un intervalo dado? Tardariamos mucho si el intervalo es muy grande. Asi que lo mejor para este caso es usar el algoritmo de la criba de eratostenes.

Lo que se hace, es tomar un primo y tachar todos los multiplos de ese primo, luego tomamos el siguiente numero no tachado(que seria un primo) y eliminamos todos sus multiplos, y asi sucesivamente, hasta que todos los no primos se hayan tachado en el intervalo. Pero como sabemos eso? Pues bien, esto lo sabemos porque como se dijo antes solo necesitamos iterar hasta la raiz de un numero para saber si es primo. Es decir que cuando lleguemos a la raiz del maximo numero del intervalo habremos eliminado todos los no primos.

Asi pues, el algoritmo en java para hacer esto seria:

public static boolean criba(int n){
 boolean primos[] = new boolean[n+1];
 Arrays.fill(primos,true);
 primos[0] = primos[1] = false;
 for(int i=2;i<(int)Math.sqrt(n)+1;i++)
  if(primos[i])
   for(int j=i*i;j<primos.length;j+=i)
    primos[j] = false;
 return primos;
}

Con el primer ciclo recorremos los numeros hasta la raiz cuadrada, y con el segundo tachamos sus multiplos si el numero "i" es primo. De esta forma los valores que queden en true seran los primos, es decir primos[2] sera true.

El algoritmo en C podria ser algo como lo siguiente:

char* criba(int n){
 char *p = (char*)malloc((n+1)*sizeof(char));
 memset(p,' ', n+1);
 n = n+1;
 int i=0,j=0;
 int f = sqrt((double)n)+1;
 p[0] = p[1] = 'n';
 for(i=0;i<f;i++)
  if(p[i]==' ')
   for(j=i*i;j<n;j+=i)
    p[j]='n';
 return p;
}

Y en C los valores que queden con una 'n', no seran primos y los que queden con ' ' seran los primos, eso ya es de gustos :)

Si hay alguna pregunta o algo que agregar, comenten.

PD: les dejo unos cuantos problemas en los cuales hay que aplicar la criba para resolverlos.
http://www.codechef.com/problems/PRPALIN
http://projecteuler.net/problem=7
http://projecteuler.net/problem=10
http://projecteuler.net/problem=249

Exponenciacion binaria y modular

Hola, estuve haciendo un par de cosas y tuve que usar un algoritmo de exponenciacion binaria y modular pero no queria que fuera recursivo asi que luego de algunos intentos, esto fue lo que consegui, espero les pueda servir de ayuda, tanto como a mi(aunque esta en java se entiende si manejas otro lenguaje :P) :

public static int expomod(int a, long b,int mod){
    int res = 1;
    while(b>0){
        if((b&1)==1)
            res=(a*res)%mod;
    b>>=1;
    a=((a%mod)*(a%mod))%mod;
    }
return res;
}

y el algoritmo en python es:

def ex(a, b,m):
     r = 1
     while(b):
             if(b&1):
                     r = (r*a)%m
             b>>=1
             a = ((a%m)*(a%m))%m
     return r

La verdad luego de ver el algoritmo recursivo, se entiende este. Lo que se hace es cambiar la recursividad a las variables, por decirlo de alguna forma. Saludos y espero sus comentarios!

Un buen tutorial donde se tratan a fondo otros algoritmos relacionados es este de topcoder.

Nota: un problema en donde se puede aplicar este algoritmo es este.