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; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La variante más simple del problema es la búsqueda de un número en un vector.

¨*Búsqueda binaria o dicotómica*¨

Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.

Está altamente recomendado para buscar en arrays de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).

Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el array.

Pseudocodigo😀

Datos de entrada:

vec: vector en el que se desea buscar el dato

tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive.

dato: elemento que se quiere buscar.

Variables

centro: subíndice central del intervalo

inf: límite inferior del intervalo

sup: límite superior del intervalo

inf = 0

sup = tam-1

Mientras inf <= sup:

centro = ((sup – inf) / 2) + inf // División entera: se trunca la fracción

Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario:

Si dato < vec[centro] entonces:

sup = centro – 1

En caso contrario:

inf = centro + 1

Fin (Mientras)

Devolver Falso

en otras palabras…

Comparamos el valor con el elemento en el medio

! Según si es mayor o menor a los que buscamos,

seguimos recursivamente con la mitad que

corresponde

! Si es igual, ya terminamos y devolvemos “verdad”

int desde,hasta,medio,elemento,posicion; // desde y

      // hasta indican los límites del array que se está mirando.

int array[N];

// Dar valor a elemento.

for(desde=0,hasta=N-1;desde<=hasta;) {

   if(desde==hasta) // si el array sólo tiene un elemento:
   {
      if(array[desde]==elemento) // si es la solución:
         posicion=desde; // darle el valor.
      else // si no es el valor:
         posicion=−1; // no está en el array.
      break; // Salir del bucle.
    }
   medio=(desde+hasta)/2; // Divide el array en dos.
   if(array[medio]==elemento) // Si coincide con el central:
   {
      posicion=medio; // ese es la solución
      break; // y sale del bucle.
    }
   else if(array[medio]>elemento) // si es menor:
      hasta=medio-1; // elige el array izquierda.
   else // y si es mayor:
      desde=medio+1; // elige el array de la derecha.
 }

Para utilizar este algoritmo, el array debe estar ordenado. La búsqueda binaria consiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro. Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si está) en el primer subarray, y si es mayor está en el segundo. Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos:

Se toma el elemento central y se divide el array en dos: {1,2,3,4}−5-{6,7,8,9} Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4} Se vuelve a dividir el array en dos: {1}−2-{3,4} Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4} Se vuelve a dividir en dos: {}−3-{4} Como el elemento buscado coincide con el central, lo hemos encontrado.

En general, este método realiza log(2,N+1) comparaciones antes de encontrar el elemento, o antes de descubrir que no está. Este número es muy inferior que el necesario para la búsqueda lineal para casos grandes.

Este método también se puede implementar de forma recursiva, siendo la función recursiva la que divide al array en dos más pequeños.

Referencias

http://www.mitecnologico.com/Main/BusquedaBinaria

http://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda

1 comentario (+¿añadir los tuyos?)

  1. Elisa Schaeffer
    Jul 07, 2011 @ 13:39:03

    Bien; 4.

    Responder

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: