Búsqueda binaria en java
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...
Regístrate para leer el documento completo.