Métodos de Búsqueda ( secuencial, binaria, indexado, hashing)

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. Y así poder encontrar el dato requerido.

Búsqueda Binaria:

La búsqueda binaria es el método, donde si el arreglo o vector esta bien ordenado, se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.
El proceso comienza comparando el elemento central del arreglo con el elemento buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el elemento central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
Este método se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda. Los pre – requisitos para la búsqueda binaria son:
La lista debe estar ordenada, en un orden especifico de acuerdo al valor de la clave.
Debe conocerse el número de elementos.
Si el conjunto de elementos es grande, el tiempo de búsqueda se puede reducir utilizando el siguiente algoritmo de tipo divide y vencerás:
1.-Se divide el elemento en dos partes.
2.-Se determina la parte que debe contener la clave buscada.
3.-Se repite el proceso en esa parte.

Búsqueda Indexada:
En este modo de organización, al fichero le acompaña un fichero de índice que tiene la función de permitir el acceso directo a los registros del fichero de datos.El índice se puede organizar de diversas formas, las más típicas son: secuencial, multinivel y árbol.A través del índice podremos procesar un fichero de forma secuencial o de forma directa según la clave de indexación, y esto independientemente de como esté organizado el fichero por sí mismo.El índice debe estar organizado en función de alguno de los campos de los registros de datos. Se pueden tener tantos índices como se quiera variando la clave (o campo) que se emplee. El índice está formado por registros (entradas) que contienen:
Clave de organización.
Puntero(s) al fichero de datos, en concreto al registro que corresponda.

Búsqueda Hashing:
En este método se requiere que los elementos estén ordenados.
El método consiste en asignar el índice a cada elemento mediante una transformación del elemento, esto se hace mediante una función de conversión llamada función hash. Hay diferentes funciones para transformar el elemento y el número obtenido es el índice del elemento.
La principal forma de transformar el elemento es asignarlo directamente, es decir al 0 le corresponde el índice 0, al 1 el 1, y así sucesivamente pero cuando los elementos son muy grandes se desperdicia mucho espacio ya que necesitamos arreglo grandes para almacenarlos y estos quedan con muchos espacios libres, para utilizar mejor el espacio se utilizan funciones mas complejas.
La función de hash ideal debería ser biyectiva, esto es, que a cada elemento le corresponda un índice, y que a cada índice le corresponda un elemento, pero no siempre es fácil encontrar esa función, e incluso a veces es inútil, ya que puedes no saber el número de elementos a almacenar.