03.l Búsqueda binaria dentro de una lista ordenada de datos. (381) Ejemplos de la ventaja de tener ordenada una lista, la búsqueda binaria permite saber de que parte de la lista dividida en 2 está lo que buscamos y si seguimos dividiendo encontramos el resultado. contact Created,Modified 2009-04-02 12:03:42, 2009-05-07 19:12:12 Author,Nick Gustavo Guillermo Perez, (madgus) [myblog]

Búsqueda Binaria (lista ordenada)

La búsqueda binaria es un método simple que se usa para encontrar datos en una lista ordenada, el mecanismo es el siguiente...

Si tenemos una lista de n datos, ordenados de mayor a menor y queremos encontrar uno en particular, haremos una búsqueda con dos índices, o sea almacenaremos el valor del elemento comparado más grande y más pequeño hasta arrinconar el resultado o llegar a un punto donde no existe tal elemento pero los dos mas cercanos son estos índices mayor y menor.

Ilustración 2: Búsqueda binaria en una lista ordenada

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Veamos ahora un trozo de código para cuando la lista está ordenada de manera creciente y decreciente, estas dos funciones utilizan la fórmula que vimos en la ilustración anterior para calcular el índice superior e inferior, de esa manera y teniendo en cuenta que la operación de división será redondeada y sólo tendremos un número entero veamos como quedarían nuestras funciones.

Orden ascendente de Texto:

1. public static String buscar_ordenado_az(String inicio){

2. int Is=lista_elem-1;

3. int Ii=0;

4. int cmp=0;

5. int old_cmp=-1;

6. int compare;

7. while (cmp!=old_cmp){

8. old_cmp=cmp;

9. cmp=(Is-Ii)/2+Ii;

10. compare=lista[cmp].compareTo(inicio);

11. if(compare==0){return lista[cmp];}

12. if(compare<0){Ii=cmp;}

13. if(compare>0){Is=cmp;}

14. }

15. return lista[Is];

16. }

Orden descendente de texto:

1. public static String buscar_ordenado_za(String inicio){

2. int Is=lista_elem-1;

3. int Ii=0;

4. int cmp=0;

5. int old_cmp=-1;

6. int compare;

7. while (cmp!=old_cmp){

8. old_cmp=cmp;

9. cmp=(Is-Ii)/2+Ii;

10. compare=lista[cmp].compareTo(inicio);

11. if(compare==0){return lista[cmp];}

12. if(compare>0){Ii=cmp;}

13. if(compare<0){Is=cmp;}

14. }

15. return lista[Ii];

16. }

En estas dos funciones iguales, sólo cambian las comparaciones, el problema en este ejemplo es la manera en la que la función de la biblioteca efectúa la comparación, podemos crear nuestras propias funciones de comparación y evitar usar las de la biblioteca, pero, la biblioteca suele tener funciones optimizadas al nivel del sistema operativo y no la máquina virtual de Java, por lo tanto las usaremos siempre que podamos.

Nota: Queda para el lector agregar esta función al ejemplo de las listas y reconstruirla para el caso que los elementos sean números cualesquiera enteros en vez de objetos de texto.

leavecomment

---