Translate

lunes, 7 de noviembre de 2011

Algoritmo de Búsqueda Binaria

Por: Rodrigo Burgos Domínguez.

   Un algoritmo de búsqueda binaria (o corte binario) es una función para buscar un valor particular en un arreglo ordenado. Eliminando la mitad de los datos en cada paso. La búsqueda binaria encuentra la media, compara y determina si el valor se encuentra en esa posición o esta antes o después. Una Búsqueda Binaria es un ejemplo de la técnica “Divide y Conquista” (o mejor dicho “Decrece y Conquista”).


Algoritmo Iterativo

int búsqueda_binaria(vector <int> list, int val){
   int der = list.size() - 1, izq = 0, m;
   while(izq <= der){
      m = (izq + der) / 2;
      if(m == list[val]) return m; //la posición del valor
      if(m > list[val]) der = m – 1;
      else izq = m + 1;
   }  
   return -1; // no se encontro el dato :P
}




Algoritmo Recursivo

// en este algoritmo se llema la funcion como sigue
// pos = bb_rec(list, 0, list.size() - 1);

int bb_rec(vector <int> list, int izq, int der int val){
   int m = (izq + der) / 2;
   if(izq > der) return -1; // no se encontro
   if(list[m] == val) return m;
   if(list[m] < val) return bb_rec(list, m + 1, der, val);
   return bb_rec(list, izq, m – 1 , val);
}


Por ejemplo: si se quiere buscar el 10 en el siguiente arreglo:

3
5
10
15
21
50
100
1564
1565
100000
              
Paso 1: La búsqueda binaria busca la mitad:

3
5
10
15
21
50
100
1564
1565
100000

Si es el resultado devuelve su posición, en otro caso busca de que lado esta el valor, y desecha la mitad del arreglo

Paso 2: busca la mitad.

3
5
10
15

Si es el resultado devuelve su posición, en otro caso busca de que lado esta el valor, y desecha la mitad del arreglo

Paso 3: busca la mitad.

10
15

Como se encontró el resultado, se regresa su posición que es la 3.

La complejidad de la búsqueda binaria de O( log2 n ).

Por ejemplo si se quiere buscar un numero en un arreglo de 1,000,000 de números, la búsqueda binaria solo requerirá 20 pasos para encontrar el valor o determinar que no existe en el arreglo.

Nota: Recordemos que el arreglo debe estar ordenado para poder aplicar este algoritmo.

Extensión de Búsqueda binaria.

    La búsqueda binaria no tan solo nos sirve para encontrar un número en un arreglo ordenado, si no también para determinar, soluciones a problemas que su respuestas van creciendo.



Por ejemplo con una búsqueda binaria podríamos saber cual es el valor que debe tener x, para que  y = 2x sea igual a 1.3, solamente modificando alguna parte del código.

                      




     
Veamos un ejemplo de un problema del concurso local de la mixteca:

Problema I: Factorial
Time limit: 10 seg.


  Es muy común que te pidan el número de 0’s a la derecha que tiene un número factorial, el cual se define como sigue:
N! = 1*2*3*4…*N

N
N!
0’s
0
1
0
1
1
0
2
2
0
3
6
0
4
24
0
5
120
1
6
720
1
7
5040
1
8
40320
1
9
362880
1
10
3628800
2

    Pero en esta ocasión no es así, yo te doy el numero de 0’s que tiene un numero factorial, y tu debes decirme el mínimo numero factorial que tiene esa cantidad de 0’s

Input

  En la entrada te darán el numero n, que es el numero de 0’s que tiene un N!, la entrada termina cuando  n = -1

Output

  Para cada numero n debes imprimir el numero N! mínimo  que cumple con la condiciones  dadas, si no existe tal numero imprimir “No existe”.

Nota: 0 <= N <= 1012
Simple Input
Simple Output
1
100
1000000
11
-1
5!
405!
4000005!
No existe


Solucion:

Ahora podemos ver, que el numero de 0’s en un numero factorial, siempre es creciente, entonces podemos resolver este problema con una búsqueda binaria.

Solucion:
// se puede ver que para saber cuantos cero tiene un numero
// factorial, solo se requiere saber cuantos múltiplos de 5
// tiene ese numero, ya que el numero de 2’s siempre
// es menor que el de 5’s. Y para formar un 0, se necesita , que
// el numero este multiplicado por un 10

long long CerosFactorial(long long num){
  long long m5 = 5, res ;
  for( res = 0 ; m5 <= num ; res += num / m5, m5 *= 5);
  return res;
}

long long busbinaria(long long NumCeros){
    long long der = 10000000000000, izq = 0, m, cont;
    long long sol = 10000000000001;
    while(izq <= der){
        m = (izq + der) / 2 ;
        cont = CerosFactorial( m );
        if( cont == NumCeros) sol = min( sol,  m );
        if( cont <= NumCeros) der = m - 1;
        else izq = m + 1;       
   }
   return sol;
}

// si el resultado de llamar busbinaria( n ) == 10000000000001 ,
// entonces no existe un numero factoria que tenga n ceros.

Para cada caso de prueba, el total de pasos que hace este algoritmo para encontrar la solución es log2 (10000000000000) que es aproximadamente 40.