BUSQUEDA BINARIA Algoritmos

BUSQUEDA BINARIA

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 binariapor que el
algoritmo divide 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énordenados de menor a
mayor.

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 quehabria que buscar posición por posición hasta
encontrar
el
dato
que
queremos.
Solo se recorre todo el arreglo y verificamos si la
posición “i” es igual al dato que queremos buscar, el
código anteriorse puede mejorar simplemente
agregandole una bandera, pero aun asi no es lo
suficientemente bueno.

El algoritmo de busqueda binaria es el siguiente:
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 laposición centro es igual al dato que
buscamos.
Si es igual significa que encontramos el dato y retornamos centro.
4. Si son diferentes verificamos si el arreglo en la posición centro es mayor al
dato quequeremos 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 delciclo y no se encontro el
dato retornamos -1
indicando que el dato no se encuentra en el arreglo.
Supongamos que tenemos el arreglo {2, 3, 5, 7, 9, 11, 14, 18, 22, 25}
y queremos buscar el dato 18,entonces el inferior toma el valor de 0
y superior el valor de 9 (ya que es tamaño del arreglo menos 1).
Calculamos el centro, centro = (superior + inferior) / 2
centro = (9 + 0) / 2
centro = 4
división...