Ejemplo 6 - Búsqueda binaria de la posición de un elemento en un vector

Objetivo

Comprender el algoritmo de búsqueda binaria para ubicar la posición de un elemento dentro de un vector ordenado.

Enunciado

La búsqueda binaria consiste en ubicar la posición de un elemento ubicado dentro de un rango de elementos.
El rango se define mediante la posición del elemento inicial y la posición del elemento final.
La idea central detrás del algoritmo de búsqueda binaria es que con una sola comparación se logre reducir a la mitad el rango de búsqueda dentro del vector. Se elimina la mitad del rango donde se sabe que el elemento no está.

Solución

Lo anterior se logra al comparar siempre el valor buscado con el que se encuentra en la posición ubicada en la mitad del camino entre la primera y última posición del rango de valores dentro de los que se está buscando.
Si el valor es igual al encontrado se devuelve esa posición
Si es menor se busca en el nuevo rango definido desde el inicio hasta la mitad - 1 Si el valor es mayor se busca en el rango comprendido entre la mitad+1 y el final.
Si el inicio y el final llegan al mismo punto sin encontrar el elemento se devuelve una posición inválida indicando que el elemento no se encuentra en el vector
Note que el proceso es naturalmente recursivo. El método buscar es una interfaz pública para la función que se encarga de "buscar" un elemento y devolver un valor.Este método se encarga de llevar a cabo el llamado inicial al método recursivo que busca un valor dentro del rango indicado por los parámetros "inicio" y "fin". El algoritmo recursivo es buscarEntre cuya condición de parada es si el "inicio" y el "fin" se encuentran o "traslapan" (si el inicio no es menor al fin). En caso contrario la búsqueda se reduce al segmento donde podría ubicarse el elemento con el "valor" deseado.

  /** <pre>
* REQUIERE: Que el vector sea diferente de null
* EFECTUA: Retorna la posición del primer elemento con valor igual al recibido como parámetro en "valor" o -1 si no lo encontró
* buscan desde la celda de la posición "inicio" hasta la posición "final".
* Es un método recursivo privado que implementan la búsqueda binaria en un vector de ints
* MODIFICA: No modifica valores externos
* @return La posición de la celda del vector donde se ubica el valor encontrado o -1 si no lo encontró
</PRE> */
private int buscarEntre(int inicio, int fin, int valor){
int resultado = -1;
if(inicio<=fin) {
int mitad = (inicio + fin) / 2;
if(vector[mitad]==valor){
resultado = mitad;
}
else {
if(valor > vector[mitad]){
resultado = buscarEntre(mitad+1,fin, valor);
}
else {
resultado = buscarEntre(inicio,mitad-1, valor);
}
}
}
return resultado;
}
/** <pre>
* REQUIERE: Que el vector sea diferente de null
* EFECTUA: Retorna la posición del primer elemento con valor igual al recibido como parámetro en "valor" o -1 si no lo encontró
* MODIFICA: No modifica valores externos
* @return La posición de la celda del vector donde se ubica el valor encontrado o -1 si no lo encontró
</PRE> */
public int buscar(int valor){
return buscarEntre(0,vector.length-1,valor);
}

Observe la ejecución para el caso con los siguientes seis valores digitados. Antes de hacer búsqueda binaria es necesario que el vector esté ordenado por lo que se utiliza el algoritmo de ordenamiento por burbuja visto anteriormente.

Si se buscan los siguientes elementos:.

La salida a consola sería igual a la siguiente:

Código Fuente

Vector.java

PruebaBusquedaBinaria.java