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?

Se divide el vector entre 2 para poder conocer la posición central y se verifica si es el dato que se esta buscando, si es el dato que se busca regresa la posición (índice del vector), en caso de que no sea el dato que buscamos se verifica si es mayor o menor que la posición central y se vuelve a re definir la posición final o inicial según cumpla la condición.

Ejemplo de búsqueda.

Big image

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