Búsqueda binaria

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos.


La definición mas simple que podemos encontrar para este problema es la búsqueda de un numero dentro de un vector o arreglo.


Las características para poder implementar este algoritmo son las siguientes:

• Los datos deben estar contenido en un estructura de datos tipo vector
• Los datos del vector deben estar ordenados

Una vez que contamos con las características descritas, 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 redefinir la posición final o inicial según cumpla la condición.

Debido a que el vector se encuentra ordenado si el dato que buscamos es mayor a la posición central se descartan todos los datos que se encuentren en la parte inferior, de la misma manera si el dato que buscamos en menor que la posición central definida se descarta la parte superior del vector.

Una vez que encuentre el dato el método regresara la posición en que lo encontró , en caso de no encontrar el dato en el vector regresara el valor -1.

Imagen que demuestra el funcionamiento de la búsqueda binaria.

Pseudocódigo:

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 inf <= sup:

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

Aquí les dejo este vídeo que encontré en youtube, donde te explica de una manera muy simple en que consiste la búsqueda binaria, solo es de entender la lógica de este vídeo, ya que no pone números, si no monedas y billetes, pero viéndolo bien te das cuenta que los ordena de acuerdo con el valor de estos.

Si consideran que le entenderían mejor con números o les gustaría ver un ejemplo explicado con números les dejare la dirección de una pagina que encontré, esta en ingles pero no tiene mucho chiste, le pueden entender a lo que dice.

Link - Ejemplo de búsqueda binaria con números

Bueno eso seria todo por esta entrada, espero les sirva de ayuda, como verán es breve, así es mejor para un mejor entendimiento, ademas de fácil y cómodo de leer.

Referencias:

http://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda
http://www.tecn.upf.es/~vlopez/docencia/castellano/todoshtml/PIIIt1cas/node14.html
http://video.franklin.edu/Franklin/Math/170/common/mod01/binarySearchAlg.html