Métodos de búsqueda de algoritmos

Métodos de búsqueda
Búsqueda lineal
Consiste en buscar de manera secuencial un elemento, es decir, pregunta si el elemento buscado está en el primero luego el segundo el tercero y asísucesivamente hasta el final del vector.
La complejidad de este algoritmo es O(n).
Búsqueda binaria
Este método se utiliza cuando el vector esta previamente ordenado este algoritmo reduce considerablemente eltiempo de búsqueda ya que disminuye el número de iteraciones necesarias.
Este método se recomienda para Arrays de gran tamaño. Por ejemplo en uno que contenga 50.000.000 elementos, realiza comomáximo 26 comparaciones (En el peor de los casos).
Compara el elemento a buscar con un elemento del array (casi siempre el central) compara si es mayor o menor al elemento a buscar. Si es mayor buscadesde el inicio del array hasta el elemento que toma, si es menor toma del último elemento hasta el elemento tomado.
De esta forma se obtienen intervalos cada vez más pequeños, hasta que tenga unintervalo indivisible.
Método hash
Este método no requiere que el Array este ordenado.
El siguiente método nos permite encontrar directamente el registro buscado, consiste en transformar el elemento enun índice de memoria donde se almacenara, para lograr esto al elemento se le aplica una función hash.
Funciones Hash
Truncamiento: Este método ignora parte de la clave o elemento y utiliza la parterestante como índice, dependiendo del tamaño de la clave y del Array dependerá que elementos se toman de ella por ejemplo si tenemos un Array de 8 dígitos y son mil posiciones se tomara el primero,segundo y el quinto.
25698542 = 258
Plegamiento: Consiste en dividir la clave en distintos grupos y la combinación de ellos en un modo conveniente resulta el índice (comúnmente suma o multiplicación)si el valor no se encuentra en el rango del Array se trunca para que este en el rango adecuado de índices. Ejemplo: se tiene una clave de 8 dígitos y 300 posiciones.
25698542 = 256+985+42=1283 ...