Búsqueda secuencial

La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave. Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista. La situación óptima es que el registro buscado sea el primero en ser examinado. El peor caso es cuando las llaves de todos los n registros son comparados con k (lo que se busca). El caso promedio es n/2 comparaciones. Este método de búsqueda es muy lento, pero si los datos no están en orden es el único método que puede emplearse para hacer las búsquedas. Si los valores de la llave no son únicos, para encontrar todos los registros con una llave particular, se requiere buscar en toda la lista.

Mejoras en la eficiencia de la búsqueda secuencial 1) Muestreo de acceso Este método consiste en observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a las probabilidades de acceso detectadas. 2) Movimiento hacia el frente Este esquema consiste en que la lista de registros se reorganicen dinámicamente. Con este método, cada vez que búsqueda de una llave sea exitosa, el registro correspondiente se mueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que el. 3) Transposición Este es otro esquema de reorganización dinámica que consiste en que, cada vez que se lleve a cabo una búsqueda exitosa, el registro correspondiente se intercambia con el anterior. Con este procedimiento, entre mas accesos tenga el registro, mas rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere mas tiempo de actividad para reorganizar al conjunto de registros . Una ventaja de método de transposición es que no permite que el requerimiento aislado de un registro, cambie de posición todo el conjunto de registros. De hecho, un registro debe ganar poco a poco su derecho a alcanzar el inicio de la lista. 4) Ordenamiento

Una forma de reducir el numero de comparaciones esperadas cuando hay una significativa frecuencia de búsqueda sin éxito es la de ordenar los registros en base al valor de la llave. Esta técnica es útil cuando la lista es una lista de excepciones, tales como una lista de decisiones, en cuyo caso la mayoría de las búsquedas no tendrán éxito. Con este método una búsqueda sin éxito termina cuando se encuentra el primer valor de la llave mayor que el buscado, en lugar de la final de la lista.

Comparación

Búsqueda Secuencial

La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. Consiste en recorrer el arreglo elemento a

elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras

otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será

la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de

que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que

comparar el valor buscado con la mitad de los elementos del arreglo. 

El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados.

Búsqueda Secuencial Indexada

Descripción de la técnica.

Un método popular para superar las desventajas de los archivos secuenciales es el del archivo secuencial indexado; pero implica un

aumento en la cantidad de espacio requerida. 

Funciona de la siguiente manera: 

Se reserva una tabla auxiliar llamada índice además del archivo ordenado mismo. Cada elemento en el indice consta de una llave

kindex y un apuntador al registro en el archivo que corresponde a kindex. Los elementos en el indice al igual que los elementos en el

archivo, deben estar ordenados en la llave. Si el indice es de un octavo del tamaño del archivo, se representa en el indice cada octavo

registra el archivo.

Búsqueda secuencial

Búsqueda secuencial consiste en revisar elemento por elemento hasta encontrar el dato buscado, o hasta llegar al final de la lista de datos disponible.La búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal, el algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la clave indicada (k) o hasta el final de la lista.

La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se

empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.

El método de búsqueda secuencial funciona bien con arreglos pequeños o para arreglos no ordenados. Si el arreglo está ordenado, se puede utilizar la técnica de alta velocidad de búsqueda binaria, donde se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.

Algoritmo de búsqueda secuencial en un arreglo desordenado

Este algoritmo da como resultado una de dos posibles soluciones las cuales son: •Encuentra o determina la posición en la que encontró el elemento que cumple con las características deseadas.•Enviar un mensaje de error o de fracaso en caso de no encontrar el elemento deseado en el arreglo.De este modo si hubiera dos o más concurrencias del mismo valor, se encuentra la primera de ellas.Este algoritmo recibe también el nombre de secuencial con bandera por utilizar la variable auxiliar booleana, empleada para detener el ciclo en caso de que el elemento buscado haya sido encontrado.Esto hace que disminuya el número de comparaciones a realizar y por lo tanto aumenta la eficiencia del algoritmo.El método secuencial pueda también aplicarse en algoritmos ordenados.

lgoritmo de búsqueda secuencial en un arreglo ordenado

El arreglo puede estar ordenado de forma ascendentemente o de forma descendentemente. A continuación se presenta el algoritmo de búsqueda con arreglos ordenados, tomaremos únicamente la forma ordenada ascendente, ya que la forma ordenada descendente es muy similar pues tiene simples variantes.

Análisis de eficiencia

La búsqueda secuencial no es el método más eficiente para vectores con un gran número de elementos. En estos casos, el método más idóneo es el de búsqueda binaria, que presupone una ordenación previa en los elementos del vector. Este caso suele ser muy utilizado facetas de la vida diaria. Un ejemplo de ello es la búsqueda del numero de un abonado en una guía telefónica; normalmente no se busca el nombre en orden secuencial, sino que se busca en la primera o segunda mitad de la guía; una vez en esa mitad. Se vuelve a tantear en una de sus dos submitades, y así sucesivamente se repite el proceso haga que se localiza la pagina correcta 

La operación elemental seleccionada en la comparación.

* Caso Mejor: El elemento buscado está en la primera posición.Caso Mejor = 1

* Caso Peor: El elemento buscado no se encuentra en el arreglo.Caso Peor = n

* Caso Medio: El elemento buscado se encuentra en la posición i en el arreglo.Caso Medio = (1 + n) / 2

Características

* La búsqueda se puede realizar en arreglos desordenados.

* El método es totalmente confiable. 

* El número de comparaciones es significativa si el arreglo es muy grande. 

* En arreglos desordenados de N componentes puede suceder que el elemento no se encuentre, por lo tanto se harán N comparaciones al recorrer todo el arreglo 

* Cantidad mínima de comparaciones es 1. 

* Cantidad media de comparaciones es (1+N)/2. 

* Cantidad máxima de comparaciones es N.

Ventajas

* Es un método sumamente simple que resulta útil cuando se tiene un conjunto de datos pequeños (Hasta aproximadamente 500 elementos) 

* Es fácil adaptar la búsqueda secuencial para que utilice una lista enlazada ordenada, lo que hace la búsqueda más eficaz. 

* Si los datos buscados no están en orden es el único método que puede emplearse para hacer dichas búsquedas. Desventajas

* Este método tiende hacer muy lento. 

* Si los valores de la clave no son únicos, para encontrar todos los elementos con una clave particular, se requiere buscar en todo el arreglo, lo que hace el proceso muy largo.

http://html.rincondelvago.com/algoritmos-de-busqueda.html largo.