Cuestionario
1.- ¿Qué es y en qué consiste la búsqueda lineal?
El algoritmo
de búsqueda lineal busca por cada elemento de un arreglo en forma secuencial.
Si la clave de búsqueda no coincide con un elemento en el arreglo, el algoritmo
evalúa cada elemento y, cuando se llega al final del arreglo, informa al
usuario que la clave de búsqueda no está presente. Si la clave de búsqueda se
encuentra en el arreglo, el algoritmo evalúa cada elemento hasta encontrar uno
que coincida con la clave de búsqueda y devuelve el índice de ese elemento.
2.- ¿Qué es y en qué consiste la búsqueda binaria?
El algoritmo de búsqueda binaria es más eficiente que el algoritmo de búsqueda
lineal, pero requiere que el arreglo se ordene. La primera iteración de este
algoritmo evalúa el elemento medio del arreglo. Si éste coincide con la clave
de búsqueda, el algoritmo termina. Suponiendo que el arreglo se ordene en forma
ascendente, entonces si la clave de búsqueda es menor que el elemento de en
medio, no puede coincidir con ningún elemento en la segunda mitad del arreglo,
y el algoritmo continúa sólo con la primera mitad (es decir, el primer elemento
hasta, pero sin incluir, el elemento de en medio). Si la clave de búsqueda es
mayor que el elemento de en medio, no puede coincidir con ninguno de los
elementos de la primera mitad del arreglo, y el algoritmo continúa sólo con la
segunda mitad del arreglo (es decir, desde el elemento después del elemento de
en medio, hasta el último elemento). Cada iteración evalúa el valor medio de la
porción restante del arreglo. Si la clave de búsqueda no coincide con el
elemento, el algoritmo elimina la mitad de los elementos restantes. Para
terminar, el algoritmo encuentra un elemento que coincide con la clave de
búsqueda o reduce el subarreglo hasta un tamaño de cero.
El
grupo de búsquedas por transformación de llaves (Hash), aumenta la eficiencia,
en cuanto al tiempo de ejecución, ya que accede a los registros por lo general
más rápidamente, pero va a depender de su implementación.
Entre las ventajas que trae consigo están:
Entre las ventajas que trae consigo están:
- Aumentar la velocidad de ejecución, independientemente del número de elementos que contenga la lista.
- Los elementos de la lista donde se realiza la búsqueda no forzosamente deben estar clasificados. La lista de datos, puede estar en un archivo o en un arreglo.
- No se necesita recorrer todos los registros anteriores (como en la búsqueda secuencial) o realizar muchas comparaciones (como podría llegar a ser en la búsqueda binaria). Idealmente encontraría directamente el registro que se está buscando.
Las funciones de Hash, para lograr su objetivo de proporcionar la
dirección donde debe estar el elemento buscado a partir de su llave, lo logran
haciendo algunas operaciones sobre los caracteres que la componen. Es
importante hacer notar que la misma función de Hash, que se utiliza, para almacenar,
es la misma que se ocupa para recuperar la llave. Cuando se transforma la llave
por el método de suma, por ejemplo al sumar el primer dígito con el tercero,
dará como resultado la dirección donde se almacenará el registro, pero se puede
presentar el caso de que la dirección ya esté ocupada por otro elemento.
4.- ¿Cuál es el algoritmo para la búsqueda
secuencial (lineal)?
inicio
i=0
i=0
bandera = 0
mientras i < n
si k [ i] = x
inicio
desplegar “búsqueda exitosa y el dato es” x
desplegar “y se encuentra en la posición” i i=n
bandera = 1
else
i=i+1
fin
fin
si bandera = 0
desplegar “no se encontró el dato en la lista”
fin
inicio
LI
= 0
LS
= n – 1
mientras
LI ~LS
M
= Parte Entera (LI + LS) /2)
si
dato< lista[M]
LS
= M -1
en
caso contrario si dato> lista [M]
LI
= M +1
en
caso contrario
desplegar
“el elemento buscado está en la posición”, M
break
fin
desplegar
“el elemento” dato “no se encontró en la lista”
1.
El
arreglo debe estar previamente ordenado
2.
Se
compara el dato con la posición del centro
3.
Si
coinciden hemos encontrado el dato
4.
Si no:
4.1
Si el dato
es menor al del centro, se busca en la primera mitad del arreglo
4.2
Si el
dato es mayor al del centro, se busca en la segunda mitad del arerglo
No hay comentarios.:
Publicar un comentario