Metodos De Besqueda

MÉTODOS DE BÚSQUEDA

Los métodos de búsqueda nos permiten recuperar información de un vector o un archivo,

que contenga una lista de datos. Por ejemplo se puede obtener el nombre y el número

telefónico de nuestra agenda de contactos o la nota obtenida por un alumno en la lista de

un curso.

Cuando se realizan búsquedas sobre vectores, se desea es encontrar la posición que

ocupa el elemento buscado dentro de la lista de elementos que contiene el vector. Para la

búsqueda de información en archivos es necesario realizar la búsqueda a partir de un

campo clave dentro del archivo.

Existen diferentes métodos de búsqueda y se puede determinar con cual método trabajar

dependiendo de la cantidad de elementos que existan en el vector o la organización de

dichos elementos.

Secuencial.

El método de búsqueda secuencial consiste en revisar la estructura de datos elemento por elemento hasta encontrar el dato que estamos buscando, o hasta llegar al final de la estructura de datos.

Normalmente cuando una función de búsqueda concluye con éxito, lo que interesa es conocer en qué posición fue encontrado el elemento buscado.

La búsqueda secuencial se puede aplicar a estructuras de datos ordenadas o desordenadas.

Si se aplica a una estructura desordenada y el elemento que se está buscando existe más de una vez en la estructura, el proceso de búsqueda debe continuar hasta que se llegue al fin de la estructura.

Ejemplo. Si tenemos una estructura con los elementos 5, 8, 3, 2, 9, 5, 7, 0, 5, 1 y estamos buscando el número 5, el resultado de la búsqueda nos mostraría las posiciones 0, 5 y 8 y el proceso terminaría al llegar al numero 1 que es el ultimo de la lista de elementos.

Elementos 5 8 3 2 9 5 7 0 5 1 Posiciones 0 1 2 3 4 5 6 7 8 9 Posiciones donde √ × × × × √ × × √ ×

encontró el número 5

Ejercicio. Crear un programa que aplique una búsqueda secuencial de un dato dentro de un arreglo de elementos desordenados y presenta la o las posiciones donde encontró el dato.

En cambio con una estructura ordenada al encontrar el elemento por primera vez podemos suponer que una vez que el elemento ya no sea igual al que estamos buscando, ya no es necesario llegar hasta el fin de la estructura.

Ejemplo. Si tenemos la estructura anterior pero ordenada 0, 1, 2, 3, 5, 5, 5, 7, 8, 9 y estamos buscando el mismo número 5, el resultado de la búsqueda nos mostraría las posiciones 4, 5, y 6, y el proceso terminaría ya que el número 7 no es menor ni igual al que estamos buscando.

Elementos 0 1 2 3 5 5 5 7 8 9 Posiciones 0 1 2 3 4 5 6 7 8 9 Posiciones donde

encontró el número 5

× × × × √ √ √ ×

Ejercicio. Crear un programa que aplique una búsqueda secuencial de un dato dentro de un arreglo de elementos ordenados y presenta la o las posiciones donde encontró el dato.

Binaria.

El método de búsqueda binaria divide el total de los elementos en dos, comparando el elemento buscado con el central, en caso de no ser iguales, se determina si el elemento buscado es menor o mayor al central, para determinar si la búsqueda continua del lado izquierdo (menor) o derecho (mayor) del central, repitiendo el mismo proceso de división y comparación, hasta encontrar el elemento buscado o que la división ya no sea posible.

Debemos destacar que este método de búsqueda solo funciona con estructuras de datos previamente ordenadas, dividiendo cada vez a la mitad el proceso de búsqueda, lo que hace que el método sea más eficiente.

Ejemplo. Si tenemos una estructura ordenada 0, 1, 2, 3, 5, 5, 5, 7, 8, 9 y estamos buscando el número 5, el resultado de la búsqueda nos mostraría la posicione 4 y el proceso terminaría ya que el elemento buscado no es diferente al que esta en la posición central.

Elementos 0 1 2 3 5 5 5 7 8 9 Posiciones 0 1 2 3 4 5 6 7 8 9 Posiciones donde i √ F

encontró el número 5

Este proceso debe sumar la posición inicial y la final, dividiendo el resultado de la suma entre dos para obtener la posición central generada por el cociente de la división, en este caso es (0+9)/2 = 4, esta posición se compara con el elemento que estamos buscando y como son iguales la búsqueda se detiene mostrando la posición donde lo encontró.

Ejercicio. Crear un programa que aplique una búsqueda binaria de un dato dentro de un arreglo de elementos ordenados y presenta la posición donde encontró el dato.

Hash.

El método de búsqueda hash o por transformación de clave aumenta la velocidad de búsqueda sin necesidad de que los elementos estén previamente ordenados, comparándolo con los métodos anteriores. Además tiene la ventaja de que el tiempo de búsqueda es independiente del número de elementos de la estructura que los almacena.

Este método 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.

Para trabajar con este método de búsqueda debe elegir previamente dos cosas:

- Una función hash que sea facil de calcular y que distribuya uniformemente las direcciones.

- Un método para resolver colisiones, generando posiciones alternativas.

Para encontrar la función hash no existe una regla que permita determinar cuál será la función más apropiada para generar un conjunto de claves que aseguren la máxima uniformidad en la distribución de las mismas. Algunas de las funciones hash más utilizadas son las siguientes:

- Función módulo (por división).

- Función cuadrada.

- Función plegamiento.

- Función truncamiento.

La función módulo o por división toma el residuo de la división entre la clave y el total de elementos de la estructura, generando la siguiente fórmula:

dirección = (clave % total elementos)

Para lograr una mayor

...