Imaginemos un mundo libre

La paz interior comienza en el momento en el que decides no permitir, que ninguna persona o evento, tome el control de tus emociones.

Algoritmos de búsqueda – Haskell

leave a comment »

En la ciencias de la Computación, y la clasificación de algoritmos, los algoritmos de búsqueda son imprescindibles y son una de las operaciones más importantes en el procesamiento de la información ya que continuamente nos vemos en la necesidad de buscar información.

Un algoritmo de búsqueda consiste en buscar en un elemento en una estructura de datos (listas , arrays, matrices, etc) y devolvernos un valor booleano en el caso de la existencia o no del elemento. Los algoritmos de búsqueda tienen 2 objetivos primordiales:

  • Determinar si el elemento buscado se encuentra o no en la estructura.
  • En el caso que se encuentre el elemento, devolver la posición en la que se encuentra.

Ahora veremos la implementación en Haskell de 2 algoritmos de búsqueda muy conocidos:

Búsqueda Secuencial.- Este es un tipo de algoritmo en el cual se explora consecutivamente todos los elementos de un conjunto. La comprobacion se realiza desde el primer elemento hasta el último, en el caso que se encuentre el elemento buscado el algoritmo se detiene. Este algoritmo tiene una complejidad en el mejor de los casos de Ω(1) y en el peor de los casos O(n).

En código haskell:

busSec::Ord a=>[a]->a->Bool
busSec [] _ = False
busSec (x:xs) ele
| x==ele = True
| True = busSec xs ele

Main> busSec [48,59,63,12,45,8,5,36,25,120] 41
False
Main> busSec [48,59,63,12,45,8,5,36,25,120] 25
True

Como lo dije anteriormente con Ord indicamos que ‘a’ puede ser un dato de cualquier tipo. El caso base es si la lista está vacía o no indicamos el elemento a buscar, en estos caso el algoritmo retorna False.

Sino se da el caso base, entonces separamos cabeza y cola y se empieza a preguntar, si el elemento es igual a la cabeza devuelve True, caso contrario que siga buscando recursivamente en la cola hasta encontrarlo. Sencillo no?.

Búsqueda Binaria: Este es un tipo de algoritmo en el cual se parte de la premisa de que una determinada lista de elementos se encuentra ordenada y además de ello se conoce su número de elementos. Este algoritmo tiene una complejidad en el mejor de los casos de Ω(1) y en el peor de los casos O(log n).

En código haskell:

busBin::Ord a=>[a]->a->Int->Int->Bool
busBin [] _ _ _ = error (“please,check your code”)
busBin vector ele ini fin
| ini > fin = False
| ele == vector!!medio = True
| ele > vector!!medio = busBin vector ele (medio+1) fin
| True = busBin vector ele ini (medio-1)
where
medio = (div(ini+fin) 2)

Main> busBin [‘a’,’b’,’c’,’d’,’e’,’f’,’g’,’h’,’i’,’j’,’k’,’l’,’m’,’n’,’o’,’p’,’q’,’r’,’s’,’t’,’u’,’v’,’w’,’x’,’y’,’z’] ‘f’ 1 25
True
Main> busBin [‘a’,’b’,’c’,’d’,’e’,’f’,’g’,’h’,’i’,’j’,’k’,’l’,’m’,’n’,’o’,’p’,’q’,’r’,’s’,’t’,’u’,’v’,’w’,’x’,’y’,’z’] ‘ñ’ 1 25
False

Explicaré como funciona:

  1. Es necesario pasarle 4 parámetros a la función busBin: El vector (conjunto de elementos), el elemento a buscar, el inicio y fin del vector, en este caso del abecedario, 1 y 25 respectivamente.
  2. A nosotros nos interesa la posición del elemento que se encuentra en el medio del vector. Para a partir de ello empezar a buscar a su izquierda o a su derecha o detenerse en el caso que el elemento a buscar sea igual al del medio.
  3. El elemento del medio lo calculamos con :(inicio + fin) /2.
  4. El algoritmo pregunta si el elemento a buscar es el del medio, si es asi, simplemente retorna true y se detiene.
  5. Si no, preguntamos si el elemento a buscar es mayor al elemento del medio, entonces volvemos a llamar a la función recursivamente y tendriamos como parámetros: vector ele (medio+1) fin, es decir se buscaría en el vector desde un elemento después del medio hacia la derecha.
  6. En caso contrario, la función tendria como parámetros: vector ele ini (medio-1) , es decir se buscaría desde el inicio hasta un elemento antes del medio.

Gracias por tu visita al blog. Puedes seguirme en Twitter haciendo click en el siguiente enlace:

Written by Ronny Yabar

December 10, 2007 at 6:04 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: