Archive | Applets RSS for this section

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

 

 

 

Applet Basico – JOptionPane

Un applet muy simple que realiza la sumatoria de 2 numeros de punto flotante
mediante el ingreso por ventanas de dialogo (JOptionPane.showInputDialog) y
posteriormente mostramos su resultado dentro de un recuadro en el applet.

Leer Más…