Algoritmo de búsqueda

Algoritmo de búsqueda
Para otros usos de este término, véase Búsqueda.

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 secuencial

Se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta encontrarlo, o hasta que se llegue al final. La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo. A continuación se muestra el pseudocódigo del algoritmo:[cita requerida]

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
  pos: posición actual en el arreglo

pos = 0
Mientras pos < tam:
 Si vec[pos] == dato devolver verdadero y/o pos, de lo contrario:
 pos = pos + 1
Fin (Mientras)
Devolver falso,

Búsqueda dicotómica (binaria)

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.

A continuación se presenta el pseudocódigo del algoritmo, tomando como elemento inicial el elemento central del array.

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
Implementación recursiva en C++ [cita requerida]
#include <iostream>
#include <vector>
bool busqueda_dicotomica(const vector<int> &v, int principio, int fin, int &x){
    bool res;
    if(principio <= fin){
        int m = (principio + fin)/2;
        if(x < v[m]) res = busqueda_dicotomica(v, principio, m-1, x);
        else if(x > v[m]) res = busqueda_dicotomica(v, m+1, fin, x);
        else res = true;
    }else res = false;
    return res;
}
/*{Post: Si se encuentra devuelve true, sino false}*/

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Algoritmo de búsqueda A* — Ejemplo de aplicación del algoritmo A*. El algoritmo de búsqueda A* (pronunciado A asterisco o A estrella ) se clasifica dentro de los algoritmos de búsqueda en grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y… …   Wikipedia Español

  • Algoritmo de búsqueda de cadenas Boyer-Moore — El algoritmo de búsqueda de cadenas Boyer Moore es un particularmente eficiente algoritmo de búsqueda de cadenas, y ha sido el punto de referencia estándar para la literatura de búsqueda de cadenas práctica.[1] Fue desarrollado por Bob Boyer y J… …   Wikipedia Español

  • Algoritmo de Dijkstra — Ejecución del algoritmo de Dijkstra Tipo Algoritmo de búsqueda Problema que resuelve Problema del camino más corto …   Wikipedia Español

  • Búsqueda — Saltar a navegación, búsqueda Búsqueda puede hacer referencia a: Busca, acción de buscar. Motor de búsqueda, sistema informático que indexa archivos almacenados en servidores web gracias a su «spider» (o Web crawler). Búsqueda binaria o Algoritmo …   Wikipedia Español

  • Búsqueda en anchura — Saltar a navegación, búsqueda Para otros usos de este término, véase Búsqueda. En Ciencias de la Computación, Búsqueda en anchura (en inglés BFS Breadth First Search) es un algoritmo para recorrer o buscar elementos en un grafo (usado… …   Wikipedia Español

  • Búsqueda en profundidad — Saltar a navegación, búsqueda Para otros usos de este término, véase Búsqueda. Una Búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo o árbol de manera ordenada, pero no… …   Wikipedia Español

  • Algoritmo evolutivo — Los algoritmos evolutivos son métodos de optimización y búsqueda de soluciones basados en los postulados de la evolución biológica. En ellos se mantiene un conjunto de entidades que representan posibles soluciones, las cuales se mezclan, y… …   Wikipedia Español

  • Algoritmo de recocido simulado — Simulated annealing (SA) o recocido simulado es un algoritmo de búsqueda meta heurística para problemas de optimización global; el objetivo geneneral de este tipo de algoritmos es encontrar una buena aproximación al valor óptimo de una función en …   Wikipedia Español

  • Algoritmo — Los diagramas de flujo sirven para representar algoritmos de manera gráfica. En matemáticas, ciencias de la computación y disciplinas relacionadas, un algoritmo (del griego y latín, dixit algorithmus y éste a su vez del matemático persa Al… …   Wikipedia Español

  • Algoritmo de Gauss-Newton — En matemáticas, el algoritmo de Gauss Newton se utiliza para resolver problemas no lineales de mínimos cuadrados. Es una modificación del método de optimización de Newton que no usa segundas derivadas y se debe a Carl Friedrich Gauss. El problema …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”