Búsqueda Binaria

La búsqueda binaria consiste en localizar el término buscado comparándolo con la mediana del conjunto de elementos previamente ordenados, reduciendo así sucesivamente el intervalo de búsqueda.

Ejemplo, dado el siguiente vector:

Suponiendo que buscamos el 5, efectuaremos los siguientes pasos:

1. Determinamos la mediana entre todos los elementos, en este caso el 20
2. nos preguntamos si 5 menor igual a 20
3. como 5 es menor que 20 reducimos el intervalo de búsqueda a los 6 primeros números
4. determinamos la nueva mediana, en este caso 9
5. nos preguntamos si 5 menor igual a 9
6. como 5 es menor que 9 reducimos el intervalo de búsqueda a los 3 primeros números
7. determinamos la nueva mediana, en este caso 3
8. nos preguntamos si 5 menor igual a 3
9. como 5 no es menor que 3 reducimos el intervalo de búsqueda a los números mayores que 3 y menores que 9, en este caso abarcamos un intervalo de un elemento, que el es 5
10. determinamos la nueva mediana de este intervalo, en este caso 5
11. nos preguntamos si 5 menor igual a 5
12. como 5 es igual a 5, hemos terminado nuestra búsqueda

A continuación se muestra el diagrama de flujo de Busqueda Binaria suponiendo que buscamos el valor Valor dentro del arreglo X[ ]:

A continuación se muestra un fragmento de código en C correspondiente al diagrama de flujo anterior:

.
.
.
int i;
float valor;
float X[N];
int alto,central,bajo;
.
.
.
bajo=0;
alto=N-1;
central=(bajo+alto)/2;

while(bajo<=alto&&X[central]!=valor)
  {
	if(valor<X[central]) alto=central-1;
	else bajo=central+1;
	central=(bajo+alto)/2;
  }
	if(valor==X[central]) printf("El valor se encuentra
					en la posición %i",central);
else printf("El valor no se encuentra");
.
.
.

Código completos: busqbina.zip