Información del Blog

Blog de carácter educativo correspondiente a la materia "Estructura de datos" , y enfocado únicamente en el Tema 6: Métodos de Búsqueda donde se desarrollaran los sub-temas:

• Búsqueda secuencial
• Búsqueda Binaria
• Búsqueda por funciones de Hash

En cada entrada contara con información relevante, ejemplos, ilustraciones y vídeos para apoyar la comprensión del tema.

Blog a cargo de 

Carlos Jesús Arroyo Vázquez

Lucero Sánchez Pineda

Servando Jaimes Moreno

Search methods: introduction

Introduction.

In many times the programmers work with large amounts of stored data in arrays and registers, so it will be necessary to determine if an array contains a value that matches a certain key value.


The process of finding a specific element of an array is called “search”.

To search for data and elements, there are several search methods.

• Sequential search 
• Binary Search 
• Search by hash functions

6.1 Búsqueda Secuencial

Búsqueda Secuencial


* “La búsqueda secuencial consiste en revisar elemento tras elemento hasta encontrar el dato buscado, o llegar al final del conjunto de datos disponible”.

Esto se hace recorriendo el arreglo y deteniéndose en cada elemento y hacer la comparación, en caso de resultar verdadera; guardar la posición del elemento o dato.

Video externo demostrativo

IMPLEMENTACIÓN EN JAVA

Basica: Es la forma mas sencilla de implementar la búsqueda secuencial.

public int busquedaSecuencial1(int arr [], int n){

        int posicion=-1;

        for (int i = 0; i < arr.length; i++) {

            if(arr[i]==n){

                posicion=i;

                break;

            }

        }

        return posicion;

    }

Compleja: De esta manera se puede tener un grado de complejidad mayor en el codigo.

 public void busquedaSecuencial2(int arr [], int n){

        int cantidad=0;

        String posiciones="";

        for (int i = 0; i < arr.length; i++) {

            if(arr[i]==n){

                cantidad++;

                posiciones+=i+"  ";

            }

        }

        if(cantidad>0){

            System.out.println("Existen "+cantidad+" numeros "+n+" en las posiciones "+posiciones);

        }else{

            System.out.println("No fue encontrado ningun "+n+" en el arreglo");

        }     

    }

VENTAJAS

• Es el método mas sencillo de comprender e implementar.
• Funciona para datos ordenados y desordenados.
• Funciona con arreglos (vectores y matrices) y con listas enlazadas (pilas, listas, colas).

DESVENTAJAS

• Es el método mas lento en tiempos de ejecución.  
• Si el valor a buscar no es único, para encontrar todos los elementos con una clave particular, se requiere buscar en todo el arreglo, lo que hace el proceso muy largo.

6.2 BUSQUE BINARIA

6.2 Búsqueda Binaria

Este método requiere que los valores en el arreglo estén ordenados.

La búsqueda binaria consiste en dividir el intervalo de búsqueda en dos partes, comparando el elemento buscado con el que ocupa la posición central en el arreglo. Para el caso de que no fueran iguales se redefinen los extremos del intervalo , según el elemento central sea mayor o menor que el elemento buscado, disminuyendo de esta forma el espacio de búsqueda. El proceso concluye cuando el elemento es encontrado, o cuando el intervalo de búsqueda termina.

Ejemplo de la vida cotidiana

*”Una búsqueda binaria típica es la búsqueda de una palabra en un diccionario. Dada la palabra, se abre el libro cerca del principio, del centro o del final dependiendo de la primera letra de la palabra que busca. Se puede tener suerte y acertar con la pagina correcta pero, normalmente no será así y el lector se mueve a la pagina anterior o posterior del libro. El proceso continua asta que se encuentre la pagina buscada o hasta que se descubre que la palabra no esta en la lista”

Ejemplo en un vector








Numero a buscar : 76
índice medio= (índice inicial+ índice final)/2

índice medio= (0+14)/2= 7
47=76 false
47<76 true
(índice inicial=8, índice final= 14)

medio=(2+14)/2= 11
77=76 false
77<76 false
77>76 true
(índice inicial= 8, índice final=11)

medio=(8+11)/2= 9
64=76 false
64<76 true
(índice inicial=9, índice final=11)

medio=(9+11)/2= 10

76=76 true

Implementacion en Java

public static int busquedaBinaria(int  vector[], int dato){

  int n = vector.length;

  int centro,inf=0,sup=n-1;

   while(inf<=sup){

     centro=(sup+inf)/2;

     if(vector[centro]==dato) return centro;

     else if(dato < vector [centro] ){

        sup=centro-1;

     }

     else {

       inf=centro+1;

     }

   }

   return -1;

 }

Ventajas y desventajas

Ventajas

•  Es notablemente mas rápido que el método secuencial.
• Es muy útil en archivos extensos y grandes cantidades de datos.
•  El código del procedimiento de esta búsqueda es corto en comparación con las demás técnicas de búsqueda

Desventajas

• El arreglo o archivo tiene que estar ordenado.
• No revisa todos los elementos del arreglo

6.3 Búsqueda por funciones de Hash

Búsqueda por funciones de Hash 

Es un método 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. Esta correspondencia se realiza mediante una función de conversión, llamada función hash.

*”Supongamos que tiene una colección de datos, cada uno de ellos es identificado por una clave. Es claro que resulta atractivo tener acceso a ellos de manera directa; es decir, sin recorrer algunos datos antes de localizar el buscado. El método por transformación de claves permite realizar justamente esta actividad; es decir localizar el dato en forma directa. El método trabaja utilizando una función que convierte una clave dada en una dirección -índice- dentro del arreglo.”

La función hash (h) aplicada a la clave genera un índice del arreglo que permite acceder directamente al elemento.
i=H(clave)

Esta función hash debe de ser simple de calcular y asignar direcciones de la manera mas uniforme posible. Es decir, debe generar posiciones diferentes dadas dos claves también diferentes:

H(k1)=i1          H(K2)=i2           K1≠K2

  
Si esta condición no ocurre hay una colisión, es decir la asignación de una misma dirección a dos o mas claves distintas.

H(K1)=1       H(K2)=i               K1≠K2

En este contexto, para trabajar con este método de búsqueda se debe seleccionar previamente:

• Una función hash que sea fácil de calcular y distribuya uniformemente las claves. 
• Un método de contingencia para resolver colisiones. Si estas se presentan, se contara con algún método que genere posiciones alternativas.

Funciones hash comunes:

• Función hash por modulo: división. 

H(K)=(KmodN)

• Función hash cuadrado. 

H(K)=digitCent(k^2)

Métodos de solución de colisión comunes:

• Reasignación lineal 
• Doble hash 
• Encadenamiento

VENTAJAS Y DESVENTAJAS

VENTAJAS

• El tiempo de búsqueda es independiente del numero de componentes del arreglo. 
• Es muy útil en archivos extensos y grandes cantidades de datos. 
• Gran versatilidad.

DESVENTAJAS

• Planteamiento e implementación complicada. 
• No merece la pena en arreglos pequeños. 
• Puede ser difícil solucionar colisiones. 
• Requiere mucho análisis de la función hash y claves a usar.

Conclusion

La búsqueda ocupa una parte importante de nuestra vida. Prácticamente todo el tiempo estamos buscando algo. El mundo 
en que se vive hoy en día es desarrollado, automatizado, y la búsqueda  de información representa un elemento de vital importancia.

En estructura de datos y la programación en general siempre se esta usando información, y en muchos casos es necesario encontrar algún dato dentro de un arreglo u archivo; y es en estos casos donde es indispensable conocer los métodos de búsqueda y saber implementarlos según la situación.

y...
 ¿Cual es tu método de búsqueda preferido?
 ¿Consideras que se pueden mejorar los existentes?
 ¿Podrías crear una función hash nueva?