METODO DE BUSQUEDA

METODOS DE BUSQUEDA INTERNO
1. Se denomina búsqueda interna cuando todos los elementos se encuentran en la memoria principal. Por ejemplo, almacenados en estructuras estáticas (arreglos) o en estructuras dinámicas (listas ligadas y arboles).
2. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.
METODO DE BUSQUEDA EXTERNOS
1. Se denomina búsqueda externa cuando todos los elementos se encuentran en memoria secundaria (archivos almacenados en dispositivos tales como cintas y discos magnéticos).
2. La búsqueda externa es aquella en la que todos los elementos se encuentran almacenados en un archivo, el cual se encuentra en un dispositivo de almacenamiento secundario como un disco duro, una cinta o una memoria USB.
PARA QUE SIRVEN LOS METODOS DE BUSQUEDA
1. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado. Son aquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accedida (posición 1, posición 500, etc).
METOD DE BUSQUEDA SECUNECIAL
1. 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.
  1. Este método consiste en recorrer el arreglo o vector elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del vector y se observa una casilla tras otra hasta que se encuentre 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 vector o arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya se en el primer elemento, como en el ultimo. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del vector.
  2. El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados.
2. CARACTERISTICAS
  1. La búsqueda se puede realizar en arreglos desordenados.
  2. El método es totalmente confiable.
  3. El número de comparaciones es significativa si el arreglo es muy grande.
  4. 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
  5. Cantidad mínima de comparaciones es 1.
  6. Cantidad media de comparaciones es (1+N)/2.
  7. Cantidad máxima de comparaciones es N.
3. VENTAJAS Y DESVENTAJAS
  1. VENTAJAS
    1. Es un método sumamente simple que resulta útil cuando se tiene un conjunto de datos pequeños (Hasta aproximadamente 500 elementos)
    2. Es fácil adaptar la búsqueda secuencial para que utilice una lista enlazada ordenada, lo que hace la búsqueda más eficaz.
    3. Si los datos buscados no están en orden es el único método que puede emplearse para hacer dichas búsquedas.
  2. DESVETAJAS
    1. Este método tiende hacer muy lento.
    2. 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.
METODO DE BUSQUEDA BINARIA
1. 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.
  1. En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este proceso, utilizando el elemento central de esa sub-lista.
    1. La búsqueda binaria es el método, donde si el arreglo o vector está bien ordenado, se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.
2. CARACTERISTAS
  1. Sirve únicamente para arreglos ordenados.
  2. Es más eficiente que el método de búsqueda secuencial, debido a que el número de comparaciones se reduce a la mitad por cada iteración del método.
  3. Cantidad mínima de comparaciones es 1.
  4. Cantidad media de comparaciones es (1+log2(N))/2.
  5. Cantidad máxima de comparaciones es log2(N).
3. VENTAJAS Y DESVENTAJAS
  1. VENTAJAS
    1. Se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda.
    2. Es el método más eficiente para encontrar elementos en un arreglo ordenado.
  2. DESVENTAJAS
    1. Este método funciona solamente con arreglos ordenados, por lo cual si nos encontramos con arreglos que no están en orden, este método, no nos ayudaría en nada.
METODO DE BUSQUE HASH
1. VENTAJAS Y DESVENTAJAS
  1. VENTAJAS
    1. Una tabla hash tiene como principal ventaja que el acceso a los datos suele ser muy rápido si se cumplen las siguientes condiciones:
    2. Una razón de ocupación no muy elevada (a partir del 75% de ocupación se producen demasiadas colisiones y la tabla se vuelve ineficiente).
    3. Una función resumen que distribuya uniformemente las claves. Si la función está mal diseñada, se producirán muchas colisiones.
  2. DESVENTAJAS
    1. Necesidad de ampliar el espacio de la tabla si el volumen de datos almacenados crece. Se trata de una operación costosa.
    2. Desaprovechamiento de la memoria. Si se reserva espacio para todos los posibles elementos, se consume más memoria de la necesaria; se suele resolver reservando espacio únicamente para punteros a los elementos.
    3. Dificultad para recorrer todos los elementos. Se suelen emplear listas para procesar la totalidad de los elementos.
2. Es un método de búsqueda que aumenta la velocidad de búsqueda, pero que no requiere que los elementos estén ordenados. Consiste en asignar a cada elemento un índice mediante una transformación del elemento.
  1. Esta correspondencia se realiza mediante una función de conversión, llamada función hash. La correspondencia más sencilla es la identidad, esto es, al número 0 se le Unidad 6. Métodos de búsqueda Pagina 9 asigna el índice 0, al elemento 1 el índice 1, y así sucesivamente. Pero si los números a almacenar son demasiado grandes esta función es inservible.
3. 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. La función de hash depende de cada problema y de cada finalidad, y se pueden utilizar con números o cadenas, pero las más utilizadas son:
  1. Restas sucesivas:
    1. esta función se emplea con claves numéricas entre las que existen huecos de tamaño conocido, obteniéndose direcciones consecutivas.
  2. Aritmética modular:
    1. el índice de un número es resto de la división de ese número entre un número N prefijado, preferentemente primo. Los números se guardarán en las direcciones de memoria de 0 a N-1. Este método tiene el problema de que cuando hay N+1 elementos, al menos un índice es señalado por dos elementos (teorema del palomar). A este fenómeno se le llama colisión, y es tratado más adelante.
  3. Mitad del cuadrado:
    1. consiste en elevar al cuadrado la clave y coger las cifras centrales.
  4. Truncamiento:
    1. consiste en ignorar parte del número y utilizar los elementos restantes como índice. También se produce colisión.
  5. Plegamiento:
    1. consiste en dividir el número en diferentes partes, y operar con ellas (normalmente con suma o multiplicación). También se produce colisión.

Next up

METODO DE BUSQUEDA

Description

Resource summary

Media attachments

Similar

	Created by JOSE ANGEL over 3 years ago