Estructuras de Datos: Métodos de Búsqueda



A menudo en informática se trabaja con grandes cantidades de datos almacenados en vectores y registros, donde es necesario determinar si un vector contiene un valor que coincida con un cierto valor clave. El proceso de encontrar un elemento específico de un vector se denomina búsqueda. La operación búsqueda nos permite encontrar datos que están previamente almacenados. La operación puede ser un éxito, si se localiza el elemento buscado o un fracaso. Dichas búsquedas se pueden realizar sobre un conjunto de datos ordenados, lo cual hace la tarea más fácil y consume menos tiempo; o se puede realizar sobre elementos desordenados, tarea más laboriosa, dependiendo al método que se esté utilizando. A continuación, se presentarán 3 métodos de búsqueda interna en un vector, con sus respectivas características y algoritmos.

Búsqueda Secuencial

     Es un método de búsqueda que se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del vector hasta encontrarlo, o hasta que se llegue al final. La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del vector.


¿Cuáles son las características de la Búsqueda Secuencial?
  • La búsqueda se puede realizar en arreglos desordenados.
  • El método es totalmente confiable.
  • El número de comparaciones es significativa si el arreglo es muy grande.
  • 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.
  • Cantidad mínima de comparaciones es 1.
  • Cantidad media de comparaciones es (1+N)/2.
  • Cantidad máxima de comparaciones es N.
  • Requiere muchas lecturas/escrituras en memoria.


¿Cuál es el algoritmo de la Búsqueda Secuencial?
Inicio
Ingresar X
Leer V(100)
Desde I = 1 hasta 100
hacer
Si V(i) = X entonces    
Imprimir “Encontrado” V(i), “Posición” i    
Fin
Fin Si
Fin desde
Imprimir “Dato no encontrado”
Fin  



Ejemplo de la Búsqueda Secuencial
Si tenemos el vector=(10,1,20,30,4)
Y deseamos buscar el elemento 20.
Comparamos 20 es igual a la posición 1: no.
20 es igual a la posición 2: no.
20 es igual a la posición 3: si.
Hemos encontrado el elemento dentro del vector.
Fin de la búsqueda


Programa de Búsqueda Secuencial

//Busqueda lineal //en un arreglo.
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
void mostrarArreglo(const int[], int); //prototipo de funcion que
recibe un arreglo constante
int busquedaLineal(const int[], int, int); //arreglo, tamano, clave
int main()
{
int clave =0;
const int tamano = 15;
int arreglo[tamano] = {25,17,13,16,41,32,12,115,95,84,54,63,78,21,10};
cout << "Elementos del arreglo: " << endl;
mostrarArreglo(arreglo,tamano);
cout << "Indique un valor a buscar y se le devolvera el indice: " << endl;
cin >> clave;
cout<< "Su valor se encuentra en
arreglo["<<busquedaLineal(arreglo,tamano,clave)<<"]"<< endl;
cout << "Fin del programa :)" << endl;
return 0;
}//fin de main
void mostrarArreglo(const int arreglo[], int tamano)
{
for (int i = 0 ; i < tamano ; i++)
cout << "arreglo[" << i <<"]=" << arreglo[i] << endl;
}
int busquedaLineal(const int arreglo[], int tamano, int clave)
{
for (int i = 0; i< tamano ; i++)
if (arreglo[i] == clave)
return i;
return -1;
}




¿Qué es la Búsqueda Binaria?

     Es un método de búsqueda que se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Para implementar este método, se compara el elemento a buscar con un elemento cualquiera del vector (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del vector que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del vector que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el vector.



¿Cuáles son las características de la Búsqueda Binaria?
  • Los datos deben estar contenidos en una estructura de datos tipo vector.
  • Los datos del vector deben estar ordenados.
  • Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.
  • Está altamente recomendado para buscar en arrays de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).


¿Cuál es el algoritmo de la Búsqueda Binaria?

     La búsqueda binaria al igual que otros algoritmos como el quicksort utiliza la técnica divide y vencerás. Uno de los requisitos antes de ejecutar la búsqueda binaria, es que el conjunto de elementos debe de estar ordenado. Supongamos que tenemos el siguiente vector.
57 53 21 37 17 36 22 3 44 97 89 26 31 47 8 17
Debemos ordenarlo
3 8 17 17 21 22 26 31 36 37 44 47 53 57 89 97

Necesitamos una seria de datos para realizar la búsqueda: El elemento en la posición inicio, fin, medio. Y porsupuesto el tamaño del vector y elemento que queremos buscar.
1
2
3
4
int first = 0;
int middle = 0;
int last = arraySize - 1;
middle = (first + last) / 2;

Preguntamos si el elemento buscado es igual al elemento que se encuentra en la posicion medio del vector, si es afirmativo ya encontramos el elemento y no hay nada más que hacer.
1
2
3
4
if (searched == array[middle]) {
cout << "Se encuentra en la posición " << middle + 1 << endl;
return array[middle];
}
Si no es así. Preguntamos si el elemento que se encuentra en la posición medio es mayor al elemento buscado, si es afirmativo y como el vector está ordenado, quiere decir que elemento buscado es menor al del medio. Entonces ahora solo buscaríamos en esa división del vector,
por lo tanto, el fin ahora sería el elemento anterior al medio.
1
2
3
if (array[middle] > searched) {
last = middle - 1;
}
De lo contrario quiere decir que elemento buscado es mayor al del medio, entonces debemos buscar en la otra división del vector, por lo tanto el inicio sería el elemento posterior al medio.
1
2
3
else {
first = middle + 1;
}
Con cualquiera de estas 2 operaciones descartamos la otra mitad del vector y por lo tanto reducimos notablemente el número de iteraciones.
Por lo tanto, en cada iteración, la búsqueda se reduce a la mitad del vector. Realizamos esto en un bucle mientras el inicio sea menor o igual al fin.



Ejemplo Gráfico de la Búsqueda Binaria




Programa de Búsqueda Binaria

#include <cstdlib> //* declaración de la librería *//
#include <iostream> //* declaración de la librería *//
#define max 100 //*se define el máximo de elementos que puede utilizar el programa; esta definición la realiza el programador *//
using namespace std;


void ingresarArreglo(float A[max],int n) //* ingreso del tamaño del vector *//
{
int i;
for(i=0;i<n;i++)
{
cout<<" A["<<i+1<<"]=";
cin>>A[i];
}
cout<<endl;
}


void reportarVector(float V[max],int n)
{
int i;
for(i=0;i<n;i++)
{
cout<< V[i]<<"\t";
}
cout<<endl<<endl;
}


void ordenarSeleccion(float V[max],int n) //*método de ordenación por selección*//
{
int i,j,k;
float temp; //*se declara una variable temporal para poder comparar con los demás elementos del vector*//


for(i=0;i<n-1;i++)
{
k=i;
temp=V[i]; //* se le asigna a la variable temporal, el primer elemento del arreglo, de manera que facilite la búsqueda del menor elemento *//

for(j=i+1;j<n;j++) //* el ciclo se inicia desde la segunda posición del vector, dado que la primera la ocupa la variable temporal *//
{
if(V[j]<temp) //* si se encontrase un valor menor al temporal, se intercambian de posición*//
{
k=j;
temp=V[j];
}
} //* por ser un ciclo, se repetirá con todos los elementos menores al temporal *//
V[k]=V[i] ;
V[i]=temp;
}
}

int busquedaBinaria(float V[max],int n ,int dato) //* método cuya función es una búsqueda binaria *//
{ //* sólo funcionará si el vector fue previamente ordenado*//
int mitad,izq,der;
izq=0;
der=n-1;
while(izq<=der) //* el elemento que esté a la izquierda debe ser menor en comparación al elemento de la derecha *//
{mitad=(izq+der)/2 //* se calcula el elemento central, hasta encontrar el elemento buscado *//
if(dato>V[mitad //* si el elemento buscado es mayor que el elemento definido en el centro, se procederá a buscar en la segunda mitad del vector *//
izq=mitad+1 //* se define al primer valor de la búsqueda como el elemento mitad + 1 *//
else if(dato<V[mitad //* si el elemento buscado es menor que el centro, se procede a buscar en la primera mitad *//
der=mitad-1;
else return mitad; //* regresa el elemento encontrado *//
}
return -1; //* indica que no existe el elemento buscado *//
}


int main(int argc, char *argv[]) //* menú principal *//
{
float A[max];
int n,p=0,dato;
int pos;
cout<<"ingrese numero de elementos :";
cin>>n;
ingresarArreglo(A,n); //* asigna al método el tamaño del vector *//
cout<<"vector ingresado"<<endl;
reportarVector(A,n); //* activa el método para su ejecución *//
ordenarSeleccion(A,n); //*activa el método para su ejecución *//
cout<<"el vector ordenado:"<<endl; //*muestra el vector ordenado *//
reportarVector(A,n);
cout<<"ingrese numero a buscar:"; //* usuario asigna el elemento a buscar dentro del vector*//
cin>>dato;
pos=busquedaBinaria(A,n,dato);
{ if(pos ==-1) //* indica que el dato no se encuentra en el vector *//
cout<<"el dato no esta en el arreglo"<<endl;
else
cout<<"el dato se encontro en la posicion:"<<pos //* muestra en cuál posición se encuenta el dato buscado *//
+1<<endl;
}
system("PAUSE");
return EXIT_SUCCESS;
}



¿Qué es una Búsqueda Hash?

    Es un método de búsqueda interno que permite que el acceso a los datos sea por una llave que indica directamente la posición donde están guardados los datos que se buscan. Prácticamente trabaja con una función que transforma la llave o dato clave en una dirección (índice) dentro de la estructura y que en ocasiones puede generar una colisión, que se define como una misma dirección para dos o más claves distintas.



¿Cuáles son las Caracterísiticas de una Búsqueda Hash?
  • Aumenta la velocidad de búsqueda sin necesidad de que los elementos estén previamente ordenados.
  • El tiempo de búsqueda es independiente del número de elementos de la estructura que los almacena.
  • No existe una regla que permita determinar cuál será la función mas apropiada para generar un conjunto de claves que aseguren la máxima uniformidad en la distribución de las mismas.



Programa de Búsqueda Hash

#include <stdlib.h>
#include <stdio.h>
//* librerías necesarias para una búsqueda hash *//
#include <time.h>
#include ``ordena.h''
#include ``hash.h''


int main(int argc,char *argv[]) //* menú principal *//
{
int num_min,num_max,incr,tamano,nveces;
char nombre[256];
short ret;
printf(``Practica numero 3, apartado 2\n'');
printf(``Realizada por: Vuestros nombres\n'');
printf(``grupo: Vuestro grupo\n'');


//* se procede a pedir al usuario los elementos para el llenado de la tabla *//
printf(``introduce el numero ninimo de elementos a
introducir en la tabla\n''); //* petición *//
scanf(``%d'',&num_min); //* recolección de datos *//
printf(``introduce el numero maximo de elementos a
introducir en la tabla\n''); //* petición *//
scanf(``%d'',&num_max); //* recolección de datos *//
printf(``introduce el incremento\n''); //* petición *//
scanf(``%d'',&incr); //* recolección de datos *//
printf(''Introduce el tamano de la tabla hash \n''); //* petición *//
scanf(``%d'',&tamano); //* recolección de datos *//
printf(``Factor del retardo\n''); //* petición *//
scanf(``%d'',&nveces); //* recolección de datos *//
printf(``Introduce el nombre del fichero\n''); //* petición *//
scanf(``%s'',nombre); //* recolección de datos *//
ret=time_Hash(nombre,num_min,num_max,incr,tamano,hash_div,n //* cálculo de los tiempos *//
veces);
if(ret==ERR) { //* si existiera un error lo muestra en pantalla *//
printf("Error en la funcion time_Hash\n");
return ERR;
}
printf(``Fichero generado correctamente\n''); //* imprime el mensaje *//
return OK:
} //* fin del código *//


Anuncio