Algoritmo de búsqueda
De Wikipedia, la enciclopedia libre
Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento concreto dentro de una estructura de datos. Consiste en solucionar un problema booleano de existencia o no de un elemento determinado en un conjunto finito de elementos, es decir al finalizar el algoritmo este debe decir si el elemento en cuestión existe o no en ese conjunto (si pertenece o no a él), además, en caso de existir, el algoritmo podría proporcionar la localización del elemento dentro del conjunto.
Este problema puede reducirse a devolver la existencia de un número en un vector.
[editar] Búsqueda secuencial (sobre un vector no ordenado)
Cuando el contenido del Vector no está o no puede ser ordenado, necesitaremos realizar una búsqueda completa, ya que, en principio, la existencia se puede asegurar desde el momento que el elemento es localizado, pero no podemos asegurar la no existencia hasta pasar por el último elemento.
La idea sería recorrer todos los elementos secuencialmente y, si el elemento es localizado, devolver verdadero (o su posición dentro del vector). Si el elemento no es localizado se sigue recorriendo todo el vector hasta llegar al último elemento y si llegamos al final y no lo hemos encontrado se devuelve falso. El algoritmo en pseudocódigo sería algo así:
Datos de Entrada:
vec: vector de enteros
tam: tamaño del vector
dato: entero que se quiere buscar dentro del vector
Variables
pos: tipo entero
pos=0
Mientras (pos<tam) Hacer
Si (vec[pos]=dato) Entonces
Devolver verdadero /* o Devolver pos, la posición del elemento localizado*/
Fin Sí
pos=pos+1
Fin Mientras
Devolver Falso /* o devolver '-1' como convenio para cuando el elemento no se haya encontrado*/
[editar] Búsqueda binaria (sobre un vector ordenado)
Cuando el Vector en el que queremos determinar la existencia o no de un elemento está ordenado, o puede estarlo, puede ser conveniente utilizar un alogritmo de Búsqueda específico. La utilización de éste permitirá reducir considerablemente el tiempo de proceso, ya que lo reduce exponencialmente.
Datos de Entrada:
vec: vector de enteros
tam: tamaño del vector
dato: entero que se quiere buscar dentro del vector
Variables
centro: tipo entero
izq: tipo entero
der: tipo entero
Mientras (izq<=der) Hacer
centro=(izq+der)/2 /* división entera: se trunca la parte decimal */
Si (vec[centro]=dato) Entonces
Devolver verdadero /* o Devolver pos, la posición del elemento localizado*/
Fin Si
Si (dato<vec[centro]) Entonces
der=centro-1
Sino
izq=centro+1
Fin Si
Fin Mientras
Devolver Falso /* o devolver '-1' como convenio para cuando el elemento no se haya encontrado*/
[editar] Enlaces externos
 |
El contenido de esta página es un esbozo sobre programación. Ampliándolo ayudarás a mejorar Wikipedia. Puedes ayudarte con las wikipedias en otras lenguas. |
