Búsqueda Binaria

Problema: dado un vector V de n elementos ordenado, escriba una función para buscar un elemento dado x en el vector V.

Ejemplos:

1. Si V[ ] = {1, 2, 5, 3, 8, 7, 10} y x = 8;

Salida: 4 , ya que el elemento x está presente en la posición 4

2. Si V[ ] = {1, 2, 5, 3, 8, 7, 10} y x = 9;

Salida: -1 , ya que el elemento x no está presente en V[ ]

Idea del algoritmo:

Sabiendo que el vector está ordenado (por ejemplo en forma creciente), se compara el elemento en la posición media del vector contra el valor buscado. Si son iguales, se termina la búsqueda porque se encontró el valor, y se puede retornar dicha posición, como la posición donde se encuentra el valor buscado en el vector. Si los valores comparados no son iguales, puede ser que el valor del medio sea mayor o menor. Si es mayor, significa que el valor buscado, si se encuentra en el vector, se encontrará a la izquierda del valor en la posición media (por lo que se puede descartar la mitad derecha del vector); mientras que si es menor, significa que el valor buscado, si está, estará a la derecha del valor en la posición media. Se actualizan los índices de referencia, y se busca en el valor en la posición media de la mitad seleccionada. Cuando el subvector en el que se busca se hace nulo, la búsqueda termina y se retorna -1, para indicar que el elemento buscado no se encuentra en el vector.

Código

Disponible en Enciclopedia Algoritmos C++

Ejemplo de uso

Disponible en ejemplo búsqueda binaria

Complejidad: O(log N)

En Ideone

Ver código y ejecución en línea en Búsqueda Binaria en Ideone

Problemas en sitios jueces que se pueden resolver con búsqueda binaria de un elemento en un vector.

• [URI Online Judge - "Dónde está la canica"] (https://www.urionlinejudge.com.br/judge/es/problems/view/1025)

Recursos Relacionados con Búsqueda Binaria

https://es.wikipedia.org/wiki/B%C3%BAsqueda_binaria

Colaborador autor del artículo: Daniel Ambort

Fecha última modificación: 26 de setiembre de 2019