UNIVERSIDAD LATINA
PROGRAMACION DE ESTRUCTURAS DE DATOS
V. MÉTODOS DE BUSQUEDA.
EI, Profesor Ramón Castro Liceaga
QUE ES UNA BÚSQUEDA ?
La búsqueda es una operación que tiene por objeto la localización de
un elemento dentro de la estructura de datos.
A menudo un programador estará trabajando con grandes
cantidades de datos almacenados en arreglos y pudiera resultar
necesario determinar si un arreglo contiene un valor que coincide
con algún valor clave o buscado.
Siendo el array de una dimensión o lista una estructura de acceso
directo y a su vez de acceso secuencial, encontramos dos técnicas
que utilizan estos dos métodos de acceso, para encontrar elementos
dentro de un array: búsqueda lineal y búsqueda binaria.
QUE ES UNA BÚSQUEDA SECUENCIAL ?
La búsqueda secuencial es la técnica más simple para buscar un
elemento en un arreglo. Consiste en recorrer el arreglo elemento a
elemento e ir comparando con el valor buscado (clave). Se empieza
con la primera casilla del arreglo y se observa una casilla tras otra
hasta que se encuentra 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 arreglo no está
en ningún orden en particular, existe la misma probabilidad de que
el valor se encuentra ya sea en el primer elemento, como en el
último.
Pseudocódigo Búsqueda Secuencial:
1.2.3.4.-
Llenar la matriz con n elementos
Mostrar los elementos
Pedir el valor a buscar
Iniciar el ciclo que recorre la matriz
Si el valor de la matriz = a buscar
- muestra el valor y su posición
- salir del ciclo
Fin_ciclo
5.- Si no hay elementos y no encontró el valor buscado
Mandar el mensaje
Programa: BuscaEnMatriz.cpp
Busca un valor en una matriz de 50 números aleatorios
QUE ES UNA BÚSQUEDA BINARIA ?
La búsqueda binaria es el método más eficiente para
encontrar elementos en un arreglo ordenado. El proceso
comienza comparando el elemento central del arreglo con
el valor buscado. Si ambos coinciden finaliza la
búsqueda. Si no ocurre así, el elemento buscado será
mayor o menor en sentido estricto que el 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.
Pseudocódigo BusquedaBinaria
(con ordenamiento de la burbuja):
1.- Inicio
2.- Declarar las siguientes funciones (prototipos)
a) ingresar.- obtener el numero que se desea busca
b) Ordenar.- ordena por el método de burbuja
c) Mostrar- muestra en pantalla el contenido de la matriz
d) Buscar.- ejecuta el algoritmo de búsqueda binaria
e) Mensaje.- presenta el mensaje inicial
3.- Declarar variables y matriz de 100 elementos
4.5.6.7.8.9.-
Mostrar mensaje de bienvenida
Inicializar el generador de números aleatoreos
Mostrar la matriz generada
Ordenar la matriz por el método de burbuja
Ingresar el numero a buscar en la matríz
Buscar el número en la matriz
Si lo encuentra mostrar posición y valor (recursivo)
Si no lo encuentra mostrar mensaje.
10.- Termina
BÚSQUEDA MEDIANTE TRANSFORMACIÓN
DE LLAVES (Hashing)
En este método se requiere que los elementos estén ordenados.
(arreglos, archivos o Bases de Datos)
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 (hash)
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.
BÚSQUEDA MEDIANTE TRANSFORMACIÓN
DE LLAVES (Función Hash)
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.
Esta función hash debe ser simple de calcular y debe
asignar direcciones de la manera más uniformemente
posible, es decir debe generar posiciones diferentes
dadas dos claves diferentes.
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:
BÚSQUEDA MEDIANTE TRANSFORMACIÓN
DE LLAVES (Función Hash)
Restas sucesivas: Esta función se emplea con claves
numéricas entre las que existen huecos de tamaño conocido,
obteniéndose direcciones consecutivas.
Aritmética modular: 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.
Colisión: Hay una colisión que se define como la asignación
de una misma dirección a dos o mas claves diferentes
BÚSQUEDA MEDIANTE TRANSFORMACIÓN
DE LLAVES (Resolución de colisiones)
Hay diferentes maneras de solucionarlas pero lo más
efectivo es en vez de crear un arreglo de número, crear un
arreglo de apuntadores, donde cada apuntador señala el
principio de una lista enlazada. Así, cada elemento que
llega a un determinado índice se pone en el último lugar de
la lista de ese índice. El tiempo de búsqueda se reduce
considerablemente, y no hace falta poner restricciones al
tamaño del arreglo, ya que se pueden añadir nodos
dinámicamente a la lista.
BÚSQUEDA MEDIANTE TRANSFORMACIÓN
DE LLAVES (Prueba)
Ejemplo:
Si la posición 397 ya estaba ocupada, el registro con clave
0596397 es colocado en la posición 398, la cual se
encuentra disponible. Una vez que el registro ha sido
insertado en esta posición, otro registro que genere la
posición 397 o la 398 es insertado en la posición siguiente
disponible.
GRACIAS…
Descargar

Métodos de búsqueda. - Docencia FCA-UNAM