Busqueda Binaria
One-dimensional arrays
¿Para que sirve?
El algoritmo de búsqueda binaria esta diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos.
Es un medio perfecto para reducir el tiempo requerido para buscar en una lista.
La búsqueda binaria no tan solo nos sirve para encontrar un número en un arreglo ordenado, sino también para determinar, soluciones a problemas que sus respuestas van creciendo.
Características para implementar este algoritmo:
- Los datos deben estar contenido en un estructura de datos tipo vector.
- Los datos del vector deben estar ordenados de manera ascendente.
¿Como funciona?
Ejemplo de búsqueda.
Pseudocodigo
Entrada:
vec: es el vector de donde se va a buscar el número deseado.
n: viene siendo el tamaño del vector, los sub-indices van desde 0 a n-1.
com: componente que se desea buscar.
Variables:
cent: sub-indice central de nuestro intervalo.
inf: limite inferior de nuestro intervalo.
sup: limite superior de nuestro intervalo.
inf = 0
sup = n - 1
Mientras que inf <= sup hacer:
cent = ((sup - inf) / 2) + inf // División: para partir la búsqueda de la mitad del vector
Si ven[cent] == com devolver: verdadero, de lo contrario:
Si com < vec[cent] entonces:
sup = cent - 1
en caso contrario:
inf = cent + 1
Fin (mientras)
devolver falso
GRUPO 6
Presentado por:
Henry Marquez
Eduardo Alvear
Juan Sarmiento
Andres Medina
Kristell Urueta
Fundación Universidad del norte
Algoritmia y programación I