Archive | diciembre 2007

Como buscar un arreglo ordenado mediante la búsqueda binaria

Como buscar un arreglo ordenado mediante la búsqueda binaria


Si el arreglo esta ordenado, podemos utilizar la técnica de búsqueda binaria de alta velocidad.El algoritmo de búsqueda binaria elimina la mitad de los elementos que se van a buscar en el arreglo, después de cada comparación.El algoritmo localiza el elemento medio del arreglo y lo compara con la clave de búsqueda.

Si son iguales, la clave de búsqueda binaria reduce el problema a buscar en la mitad del arreglo ordenado. Si la clave de búsqueda es menor que el elemento medio del arreglo, se buscara en la primera mitad del arreglo; en caso contrario, se buscara en la segunda mitad. La búsqueda continua hasta que la clave de búsqueda sea igual al elemento medio de un subarreglo, o hasta que el subarreglo consista en un elemento que no sea igual a la clave de búsqueda.

En el peor de los casos, para buscar un arreglo ordenado de 1023 elementos se requerirán solamente 10 comparaciones si se utiliza una busqueda binaria. Al dividir varias veces 1024 ente 2 ( ya que de cada comparación se elimina la mitad del arreglo) se producen estos valores 512,256,128,64,32,16,8,4,2,1. El numero 1024 (2¹º) se divide entre solo 10 veces para obtener el valor de 1. La división entre 2 es equivalente a una comparación en el algoritmo de busqueda binaria. Por lo tanto, un arreglo de 1.048.676 (2²º) elementos requiere un máximo de 20 comparaciones para encontrar la clave y un arreglo de mil millones de elementos requiere un máximo de 30 comparaciones para encontrar la clave.

Para demostrar lo anteriormente explicado dejo un ejemplo practico como siempre, espero les sea de utilidad

Saludos a todos y felices fiestas. xD

————————————————————————————————–

 

Capturas del programa.

buscar un arreglo ordenado mediante la búsqueda binaria (scr1)

buscar un arreglo ordenado mediante la búsqueda binaria (scr2)

 

DESCARGAR EL FUENTE

 

 

 

Instrucciones de Control [J2SE]

Instrucciones de Control [J2SE]

A continuacion dejo 2 brevisimos ejemplos en donde se pone en practica instrucciones de repeticion for, do … while.
Y mostramos las sentencias break y continue.

Seleccion multiple Switch

selectormultiple1.jpg

Java Cuenta con la instruccion switch de seleccion multiple para realizar distintas accione, con base en los posibles valores de una variable o explresion entera. Cada accion se asocia con un valor integral constante ( valores tipo byte, short, int o char, y no long ) que la variable o expresion pueda asumir.
Echo esta breve aclaracion o explicacion pasamos a la parte practica.
Este sencillo Applet nos da a elegir previamente en una ventana o cuadro de dialogo el grafico a ilustrar , esto puede ser opcion 1 ,2 o 3 (linea, rectangulo o circulo respectivamente) una vez elegido esto mostramos en otra ventana el proceso.
Como veremos en el codigo, tenemos un metodo switch dentro de un metodo paint que es el encargado de dibujar las lineas,rectangulos u obalos, segun la opcion elegida.
sin mas preambulos mostramos el codigo.

 Leer Más...