La búsqueda binaria consiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro. Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si está) en el primer subarray, y si es mayor está en el segundo.
Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos:
Se toma el elemento central y se divide el array en dos:
{1,2,3,4}-5-{6,7,8,9}
Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4}
Se vuelve a dividir el array en dos:
{1}-2-{3,4}
Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4}
Se vuelve a dividir en dos:
{}-3-{4}
Como el elemento buscado coincide con el central, lo hemos encontrado.
Si al final de la búsqueda todavía no lo hemos encontrado, y el subarray a dividir está vacio {}, el elemento no se encuentra en el array. La implementación sería:
int desde,hasta,medio,elemento,posicion; // desde y hasta indican los límites del array que se está mirando.
int array[N];
// Dar valor a elemento.
for(desde=0,hasta=N-1;desde<=hasta;)
{
if(desde==hasta) // si el array sólo tiene un elemento:
{
if(array[desde]==elemento) // si es la solución:
posicion=desde; // darle el valor.
else // si no es el valor:
posicion=-1; // no está en el array.
break; // Salir del bucle.
}
medio=(desde+hasta)/2; // Divide el array en dos.
if(array[medio]==elemento) // Si coincide con el central:
{
posicion=medio; // ese es la solución
break; // y sale del bucle.
}
else
if(array[medio]>elemento) // si es menor:
hasta=medio-1; // elige el array de la izquierda.
else // y si es mayor:
desde=medio+1; // elige el array de la derecha.
}
CARACTERISTICAS.- Uno de los algoritmos de búsqueda más eficiente que existe en la estructura de datos es la búsqueda binaria, las características para poder implementar este algoritmo son las siguientes:
- Los datos deben estar contenido en un estructura de datos tipo vector
- Los datos del vector deben estar ordenados
Analisis de algoritmos 