Please enable JavaScript.
Coggle requires JavaScript to display documents.
METODOS DE BUSQUEDA, ALUMNO: FELIX BARUC HERNANDEZ CORTES GRUPO: 3'4A…
METODOS DE BUSQUEDA
Técnica Secuencial Ordenada/Desordenada.
Descripción de la técnica:
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.
Ventajas de la técnica:
Es el algoritmo más simple de búsqueda y no requiere ningún proceso previo de la tabla, ni ningún conocimiento sobre la distribución de las llaves. La búsqueda secuencial es el área del problema donde previamente existían mejores algoritmos.
Principales Aplicaciones:
Los archivos secuenciales son típicamente utilizados en aplicaciones de proceso de lotes Y son óptimos para dichas aplicaciones si se procesan todos los registros. La organización secuencias de archivos es la única que es fácil de usar tanto en disco como en cinta.
Desventajas de la técnica:
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.
Si los registros a los que se accede con frecuencia no estan al principio del archivo, la cantidad promedio de comparaciones aumenta notablemente dado que se requiere mas tiempo para recuperar dichos regisros.
Técnica de 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 secuencias indexado; pero implica un aumento en la cantidad de espacio requerida.
Ventajas de la técnica:
Permite procesar el archivo secuencialmente por orden lógico y también procesarlo al azar. La ventaja real del método secuencial indexado es que los elementos en la tabla pueden ser examinados en forma secuencial si todos los registros en el archivo deben ser accesados, pero sin embargo, el tiempo de búsqueda para algún elemento en particular se reduce considerablemente.
Desventajas de la técnica:
Pero implica un aumento en la cantidad de espacio requerida, porque se ocupa un indice y “se pone a un lado además del fichero clasificado a sí mismo”.
La inserción en una tabla secuencial indexada es un poco más difícil debido a que puede qe no exista espacio entre dos entradas en la tabla, siendo necesario mover un gran número de elementos en la tabla.
Principales Aplicaciones: Un uso en la cual esta busqueda se aplica, es donde se presenta el ingreso de datos (registros) sin ningun tipo de orden especifico; pero en cada determinado momento su campo llave es almacenado en un indice, en el cual esas llaves estan ordenadas de menor a mayor o de mayor a menor dependiendo el uso que se le de. De esta manera, para agilizar la busqueda de un registro en particular se accesa a ese registro por medio de su campo llave alacenado en el indice.
Técnica de Búsqueda por Interpolación.
Descripción de la técnica: Este método se puede aplicar solamente a tablas o archivos ordenados. Como su nombre lo indica se trata de llegar al elemento buscado por medio de la interpolación lineal. El procedimiento es recursivo; como en el caso de la búsqueda binaria, en cada paso se van modificando los límites, disminuyendo el intervalo, hasta llegar al elemento buscado.
Ventajas de la técnica:
La búsqueda de interpolación, es una búsqueda mucho mejor que la binaria en la práctica porque, a menos que no sea muy grande, el valor de log2n es bastante pequeño que el logaritmo de él no es mucho más pequeño.
Incluso a pesar de qe el calclo es de algun modo mas complejo, una busqueda con interpolacion puede proporcionar una mejoria importante a nuestra busqueda binaria en grandes conjuntos de datos con claves distribuidas de modo uniforme.
Desventajas de la técnica:
La búsqueda de la interpolación requiere una aritmética más elaborada, a parte que los calculos que se necesitan para esta busqueda son muy lentos.
Para lograr esta busqueda se requieren llaves, multiplicaciones y divisiones complejas, es decir, calculos de nivel alto.
Principales Aplicaciones:
En aplicaciones matematicas donde se busquen approximaciones de alguna ecuacion, se utiliza este metodo pero sin su recursividad solo hace su primera para conseguir las approx.
Tambien tiene las mismas aplicaciones que la busqueda binaria ya que son casi iguales.
Técnica de Búsqueda Binaria.
Descripción de la técnica:
Si los datos que se buscan están clasificados en un determinado orden, el método citado anteriormente se denomina búsqueda binaria.
La búsqueda binaria utiliza un método de `divide y vencerás'para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si éste es el elemento buscado, entonces la búsqueda ha terminado.
Ventajas de la técnica.:
La búsqueda binaria es un método eficiente siempre que el vector esté ordenado. En la práctica, esto suele suceder, pero no siempre. Por esta razón la búsqueda binaria exige una ordenación previa del archivo.
La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una lista. Este método, sin embargo, exige que los datos estén ordenados.
Desventajas de la técnica.:
La búsqueda binaria tiene, sin embargo, inconvenientes a resaltar:
El archivo debe estar ordenado y el almacenamietno de un archivo ordenado suele plantear problemas en las inserciones y eliminaciones de elementos.
No revisa todos los elementos del archivo, requiere que todos los elementos esten ordenados
Esta busqueda mas de uno o dos accesos si el archivo es enorme;y mantener ese archivo ordenado es muy costoso.
ALUMNO: FELIX BARUC HERNANDEZ CORTES
GRUPO: 3'4A