Saturday, October 23, 2010

ALGORITMOS DE BÚSQUEDA

Hace algún tiempo que no posteaba en este BLOGs por temas de tiempo, pero hoy regreso a postear sobre un tema interesante y es sobre diferentes algoritmos de búsqueda que son:

- Lineal
- Binario

I.- ALGORITMO LINEAL: Es bien común y consta que la iteración de un arreglo posición por posición hasta encontrar un TRUE en lo relacionado al comparativo que se va haciendo. Este algoritmo es bueno para distancias cortas pero por ejemplo si se requiere buscar una lista cargada con 40'000 registros y el ID buscado esta en la posición 39'999, uno por uno se mandara a comparar. Esto es un problema.

II.- ALGORTIMO BINARIO: Muchos no lo conocen pero este algoritmo sale a solucionar un el gran problema que el Algoritmo Lineal tiene con las listas grandes. Este Algoritmo tiene una lógica basada en simplemente decir:

NumeroAuxiliar = ( "Numero Inicial del Arreglo" + "Numero Final del Arreglo" ) / 2


Esto automáticamente enviara el INDICE al centro del Arreglo, de ahí se tiene que realizar una validación contra el número a buscar tanto por ‘IZQ como DER':

Aquí la matriz:

NumeroBuscar > NumeroAuxiliar
INCREMENTO: posicionArreglo ++

NumeroBuscar < NumeroAuxiliar
DECREMENTO: posicionArreglo --

NumeroBuscar = NumeroAuxiliar
"NUMERO ENCONTRADO"

Esto agiliza hasta en un 70% la velocidad del motor de búsqueda:

El ejemplo continuación muestra los dos Algoritmos de Búsqueda en dos modos de realizarlo, el 1er modo utilizando comandos de iteración como el típico FOR y el 2do modo: utilizando RECURSIVIDAD. Así los ejemplos estarán a GUSTO DE TODOS.

Para probar el ejemplo simplemente descomentar el método deseado y este se ejecutara e imprimirá un LOG detallado con los resultados:

iteacion.busquedaLineal( numero, arregloNumeros );
//iteacion.busquedaBinaria( numero, arregloNumeros );
//iteacion.busquedaLinealRecursiva( numero, arregloNumeros );
//iteacion.busquedaBinariaRecursiva( numero, arregloNumeros );

public static int[] arregloNumeros = { 111, 222, 333, 444, 555, 666, 777, 888 , 999 };


- Numero Buscar: 999
- Inicio: 0
- Fin: 8
------- ORDEN: [0] -------
ES MAYOR ...!!!
999 > 111

- Numero Buscar: 999
- Inicio: 1
- Fin: 8
------- ORDEN: [1] -------
ES MAYOR ...!!!
999 > 222

- Numero Buscar: 999
- Inicio: 2
- Fin: 8
------- ORDEN: [2] -------
ES MAYOR ...!!!
999 > 333

- Numero Buscar: 999
- Inicio: 3
- Fin: 8
------- ORDEN: [3] -------
ES MAYOR ...!!!
999 > 444

- Numero Buscar: 999
- Inicio: 4
- Fin: 8
------- ORDEN: [4] -------
ES MAYOR ...!!!
999 > 555

- Numero Buscar: 999
- Inicio: 5
- Fin: 8
------- ORDEN: [5] -------
ES MAYOR ...!!!
999 > 666

- Numero Buscar: 999
- Inicio: 6
- Fin: 8
------- ORDEN: [6] -------
ES MAYOR ...!!!
999 > 777

- Numero Buscar: 999
- Inicio: 7
- Fin: 8
------- ORDEN: [7] -------
ES MAYOR ...!!!
999 > 888

- Numero Buscar: 999
- Inicio: 8
- Fin: 8
------- ENCONTRADO: [8] -------
999 = 999

---------- TOTAL DE PASOS (BUSQUEDA LINEAL): [9] ----------

- Numero Buscar: 999
- Inicio: 0
- Fin: 8
- Suma: 8
------- ORDEN: [4] -------
ES MAYOR ...!!!
999 > 555

- Numero Buscar: 999
- Inicio: 5
- Fin: 8
- Suma: 13
------- ORDEN: [6] -------
ES MAYOR ...!!!
999 > 777

- Numero Buscar: 999
- Inicio: 7
- Fin: 8
- Suma: 15
------- ORDEN: [7] -------
ES MAYOR ...!!!
999 > 888

- Numero Buscar: 999
- Inicio: 8
- Fin: 8
- Suma: 16
------- ENCONTRADO: [8] -------
999 = 999

---------- TOTAL DE PASOS (BUSQUEDA BINARIA): [4] ----------

999 != 111
999 != 222
999 != 333
999 != 444
999 != 555
999 != 666
999 != 777
999 != 888
999 == 999
---------- TOTAL DE PASOS (BUSQUEDA LINEAL RECURSIVA): [9] ----------

------- ORDEN: [4] -------
ES MAYOR ...!!!
999 > 555

------- ORDEN: [6] -------
ES MAYOR ...!!!
999 > 777

------- ORDEN: [7] -------
ES MAYOR ...!!!
999 > 888

ENCONTRADO ...!!!
999 == 999

---------- TOTAL DE PASOS (BUSQUEDA BINARIA RECURSIVA): [4] ----------

Para descarga del demo completo pulsar AQUÍ.