Comprender el algoritmo de búsqueda binaria para ubicar la posición
de un elemento dentro de un vector ordenado.
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á.
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> |
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: