Si la lista donde vamos a buscar se encuentra previamente ordenada, podemos utilizar este método que es notablemente más rápido que el anterior (corre en O(lgn)). Esta búsqueda utiliza una subcategoría especial de “Divide y Vencerás”, conocida como “Decrementa y Vencerás”.

La diferencia entre estas técnicas es que en la primera, para resolver un problema lo descomponemos en subpartes, las cuales resolvemos para obtener la solución. En la segunda, también comenzamos dividiendo el problema en subproblemas, pero en lugar de resolverlos todos, desechamos los que no son útiles para obtener la respuesta y resolvemos con los demás.

Para realizar una búsqueda binaria, lo que hacemos es lo siguiente: dividimos el arreglo en dos y tomamos la casilla que se encuentra entre estos subarreglos. Si la casilla que escogimos es igual al dato que buscamos, hemos encontrado la solución. Si ocurre que son distintos, revisamos los dos posibles casos: si la casilla es más grande que el dato que estamos buscando, las casillas mayores también lo serán y podemos desecharlas; en caso contrario nos deshacemos de las casillas menores. Después aplicamos el mismo método en las casillas restantes.

Cabe mencionar que la partición en mitades produce un resultado óptimo. Si realizamos particiones en tamaños desiguales o en más de dos partes, la complejidad del algoritmo no cambia pero las constantes se incrementan significativamente.




Solución: Tenemos que buscar las fechas de los alumnos en la lista de la maestra. Utilizando búsqueda lineal nos tardaríamos demasiado, por lo que lo vamos a hacer con una búsqueda binaria. Primero leemos la lista de la maestra y después leemos cada dato de los alumnos. Siempre que encontremos un dato en la lista, incrementamos un contador.




En las primeras tres líneas declaramos las variables a utilizar. Las variables n y m son la cantidad de fechas en la lista de la maestra y en la de los estudiantes, respectivamente. Utilizamos i para los ciclos y t para contar el total de datos en la lista de la maestra. Para guardar la lista utilizamos el arreglo lista y en x leemos el año a buscar.

A continuación tenemos la función que realiza la búsqueda binaria (líneas 5 a 18). La implementación que tenemos es iterativa y se puede hacer recursiva sin muchos problemas. Las variables sup, inf y mitad las usamos para señalar las casillas superior, inferior y media, respectivamente. Inicializamos la parte inferior a la primera casilla y la superior a la última en la línea 8.

En la línea 11 encontramos la casilla que se encuentra en medio, para después revisar si es mayor, menor o igual al dato que buscamos. En caso que sea mayor, ajustamos nuestro límite inferior a uno arriba de la mitad; si es menor, ajustamos el superior a uno abajo; si es igual, entonces hacemos que el límite superior tome el valor de –1. Esto lo repetimos hasta que el valor superior sea menor al inferior. Es importante que los límites los cambiemos uno mayor o menor a la mitad, ya que esto evita que el código se quede ciclado. Al final, sabemos que sup no puede tomar valores negativos por lo que si es igual a –1 entonces encontramos el dato, en caso contrario, devolvemos un valor que nos indique que el dato no está en el arreglo.

La siguiente parte es la parte principal del código (líneas 20 a 33). Comenzamos leyendo la cantidad de datos en la lista, para después leerla (líneas 21 a 23). A continuación leemos la cantidad de fechas en la lista de los alumnos e inicializamos el contador a cero. Para cada fecha lo que hacemos es leerla, buscarla en la lista y, en caso de encontrarla, incrementar el contador. Al final escribimos la cantidad de datos que concordaban en las dos listas.

Entrada:	10 98 486 699 1054 1097 1492 1493 1763 1982 2006 4 1492 65536 1492 100
Desarrollo:	98 486 699 1054 1097 1492 1493 1763 1982 2006 x= 1492 inf=  1, sup= 10, lista[mitad]= 1097 < 1492 inf=  6, sup= 10, lista[mitad]= 1763 > 1492 inf=  6, sup=  7, lista[mitad]= 1492 = 1492 inf=  6, sup= -1 BusqBinaria= 6 x= 65536 inf=  1, sup= 10, lista[mitad]= 1097 < 65536 inf=  6, sup= 10, lista[mitad]= 1763 < 65536 inf=  9, sup= 10, lista[mitad]= 1982 < 65536 inf= 10, sup= 10, lista[mitad]= 2006 < 65536 inf= 11, sup= 10 BusqBinaria= 0 x= 100 inf=  1, sup= 10, lista[mitad]= 1097 > 100 inf=  1, sup=  4, lista[mitad]=  486 > 100 inf=  1, sup=  1, lista[mitad]=   98 < 100 inf=  2, sup=  1 BusqBinaria= 0
Salida:	2

Lenguaje	Fecha	Tiempos [s]				Memoria [Kb]
		Ejecución	Mejor	Mediana	Peor
Pascal	28-Feb-2006	0.609	0.234	0.711	1.962	186
C	28-Feb-2006	0.546				190

Valladollid:

Ural: