04# Algoritmos de Búsqueda

Un algoritmo es como un conjunto de instrucciones que se deben seguir para realizar una tarea concreta. Este se rige por una serie de pasos o ciclos con sus condiciones definidas para el proceso del trabajo que se quiere hacer.

Hoy nos basaremos mayormente en los algoritmos de búsqueda, estos se encargan de encontrar un elemento en una estructura de datos. Existen diversos algoritmos para este propósito.

Unos de los vistos en las clases anteriores son el secuencial, binario y el de interpolación.

Secuencial:

Uno de los algoritmos más sencillos y fáciles de implementar, ya que su única función es la de comparar cada elemento de la estructura de datos con el elemento que se quiere encontrar:

L: Largo de la estructura

T: temporal contador

ELE: Elemento a buscar

A: Estructura donde se desea buscar

Mientras L > T:

                Si ELE es igual a A posición [T]:

                               Retorna ELE

                Si no:

                               Incrementa en uno a T

Retorna -1

Como vemos el algoritmo es muy sencillo, el problema con este es la capacidad de procesamiento que requiere y la pérdida de tiempo que ocasionaría utilizarlo en grandes estructuras de datos.

Binario:

Otro de los más conocidos es el algoritmo binario, este lo que hace es hacer división por 2 del arreglo y compara en cuál de las dos mitades se puede encontrar el elemento deseado, haciéndolo mucho más eficiente que el exponencial ya que acorta el tiempo y procesamiento de la búsqueda.

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

Fuente:

https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda#B.C3.BAsqueda_dicot.C3.B3mica_.28binaria.29

La condición (inconveniente en algunos casos) para utilizar este algoritmo es que la estructura que se va utilizar debe tener algún tipo de orden en los elementos que la componen.

Interpolación:

Uno de los últimos de los cuales se hablo fue el algoritmo de interpolación, este es muy similar al algoritmo binario, pero con una peculiaridad de que con una formula trata de tener un rango de donde se ubica el elemento, esto quiere decir que se obvia que los elementos de la estructura son números enteros. En este algoritmo los elementos también deben tener un tipo de orden secuencial.

Fuente: http://ingenieriacivil.tutorialesaldia.com/%C2%BFsabes-como-realizar-la-interpolacion-lineal-con-microsoft%C2%AE-excel/

Esta fórmula es la que calcula la posición promedio de donde se podría ubicar el elemento deseado.

Con el mismo procedimiento del binario, pero implementando está formula se obtiene un poco más de precisión a la hora de encontrar un elemento.

Fibonacci

“En ciencia de la computación, la técnica de búsqueda de Fibonacci es un método de búsqueda en un array ordenado usando un algoritmo de divide y vencerás que disminuye las ubicaciones posibles con la ayuda de los números de Fibonacci. Comparado con la búsqueda binaria, Fibonacci busca las ubicaciones cuyas direcciones tienen poca dispersión. Por lo tanto, cuando los elementos se buscan, tiene un acceso a memoria no uniforme (el tiempo necesario para acceder a la ubicación de almacenamiento varía en dependencia de la ubicación previamente accedida), la búsqueda de Fibonacci tiene una ventaja sobre la búsqueda binaria en disminuir ligeramente el tiempo promedio necesario para acceder a la ubicación de almacenamiento. El típico ejemplo de acceso no uniforme al almacenamiento es una cinta magnética, donde el tiempo de acceso a un elemento en particular es proporcional a su distancia desde el elemento actual apuntado por el cabezal de la cinta. Note, sin embargo, que grandes arrays no adecuados en la cache del CPU o incluso en RAM pueden ser considerados como ejemplos de acceso no uniforme. La búsqueda de Fibonacci tiene complejidad O(log(x)) (Ver notación de O Grande). La búsqueda de Fibonacci fue concebida por primera vez por Kiefer (1953) como una búsqueda minimax para el máximo (mínimo) de una función unimodal en un intervalo.”

Información tomada de Wikipedia.

Paso Inicial Fijar h > 0 y  > 0.

Elegir n tal que Fn > b−a h.

Hacer a1 = a, b1 = b, y1 = a1 + 1 − Fn−1 Fn (b1 − a1) z1 = a1 + Fn−1 Fn (b1 − a1), y k = 1.

Paso General

Repetir: 1. Si f(yk) ≥ f(zk), ir a 2.

 En caso contrario, ir a 3.

2. Hacer ak+1 = yk, bk+1 = bk, yk+1 = zk y zk+1 = ak+1 + Fn−k−1 Fn − k (bk+1 − ak+1).

Si k = n − 2, ir a 5.

En caso contrario, calcular f(zk+1) e ir a 4.

3. Hacer ak+1 = ak, bk+1 = zk, zk+1 = yk y calcular yk+1 = ak+1 + 1 − Fn−k−1 Fn − k (bk+1 − ak+1).

 Si k = n − 2, ir a 5.

En caso contrario, calcular f(zk+1) e ir a 4.

4. Hacer k = k + 1 e ir a 1.

 5. Hacer yn = yn−1, zn = yn−1 + . Si f(yn) ≤ f(zn), tomar an = an−1, bn = zn−1.

Si f(yn) ≥ f(zn), tomar an = yn−1, bn = bn−1.

FINAL. [an, bn] es el intervalo de incertidumbre final.

 7 Para un valor de n suficientemente grande, la proporción Fn−1 Fn tiende al número ´áureo, y por lo tanto el método de Fibonacci se aproxima al método de la sección ´aurea.

Su algoritmo es algo complejo, pero cuando se entiende tiene muy buena funcionalidad.

Hasta la próxima.