Búsqueda binaria en java
Páginas: 3 (699 palabras)
Publicado: 29 de noviembre de 2011
El algoritmo de búsqueda binaria es un excelente método para buscar datos dentro de una estructura(generalmente un arreglo unidimencional). Se le da el nombre de búsqueda binaria por que el algoritmodivide en dos el arregelo, aludiendo al concepto de bit, el cual puede tener dos estados.
La única condición para usar este algoritmo es que los datos dentro del arreglo estén ordenados de menor amayor.
La solución mas fácil para realizar una busqueda es por fuerza bruta, pero este método puede resultar bastante ineficiente cuando se tiene una gran cantidad de datos, ya que habria quebuscar posición por posición hasta encontrar el dato que queremos.
El código por fuerza bruta es bastante sencillo:
dijo:
for(int i=0; i<Arreglo.length; i++)
if(Arreglo ==elemento)
System.out.println("nElemento encontrado en la posicion: " + i);
Solo se recorre todo el arreglo y verificamos si la posición i es igual al dato que queremos buscar, el códigoanterior se puede mejorar simplemente agregandole una bandera, pero aun asi no es lo suficientemente bueno.
El algoritmo de busqueda binaria es el siguiente:
dijo:
1. Se declaran losíndices superior e inferior. El inferior en 0 y el superior con el
tamaño del arreglo menos 1.
2. Se calcula el centro del arreglo con la siguiente formula:
centro = (superior + inferior)/ 2
3. Verificamos si el arreglo en la posición centro es igual al dato que buscamos. Si es
igual significa que encontramos el dato y retornamos centro.
4. Si son diferentesverificamos si el arreglo en la posición centro es mayor al dato que
que queremos buscar. Si es mayor actualizamos superior: superior = centro - 1, si
no actualizamos inferior: inferior = centro +1.
5. Volvemos al paso 2.
Si cuando ya no se cumpla la condicón del ciclo y no se encontro el dato retornamos -1 indicando que el dato no se encuentra en el arreglo.
Supongamos...
La única condición para usar este algoritmo es que los datos dentro del arreglo estén ordenados de menor amayor.
La solución mas fácil para realizar una busqueda es por fuerza bruta, pero este método puede resultar bastante ineficiente cuando se tiene una gran cantidad de datos, ya que habria quebuscar posición por posición hasta encontrar el dato que queremos.
El código por fuerza bruta es bastante sencillo:
dijo:
for(int i=0; i<Arreglo.length; i++)
if(Arreglo ==elemento)
System.out.println("nElemento encontrado en la posicion: " + i);
Solo se recorre todo el arreglo y verificamos si la posición i es igual al dato que queremos buscar, el códigoanterior se puede mejorar simplemente agregandole una bandera, pero aun asi no es lo suficientemente bueno.
El algoritmo de busqueda binaria es el siguiente:
dijo:
1. Se declaran losíndices superior e inferior. El inferior en 0 y el superior con el
tamaño del arreglo menos 1.
2. Se calcula el centro del arreglo con la siguiente formula:
centro = (superior + inferior)/ 2
3. Verificamos si el arreglo en la posición centro es igual al dato que buscamos. Si es
igual significa que encontramos el dato y retornamos centro.
4. Si son diferentesverificamos si el arreglo en la posición centro es mayor al dato que
que queremos buscar. Si es mayor actualizamos superior: superior = centro - 1, si
no actualizamos inferior: inferior = centro +1.
5. Volvemos al paso 2.
Si cuando ya no se cumpla la condicón del ciclo y no se encontro el dato retornamos -1 indicando que el dato no se encuentra en el arreglo.
Supongamos...
Leer documento completo
Regístrate para leer el documento completo.