Búsquedas en arreglos

Una búsqueda es el proceso mediante el cual podemos localizar un elemento con un valor especifico dentro de un conjunto de datos. Terminamos con éxito la búsqueda cuando el elemento es encontrado.

A continuación veremos algunos de los algoritmos de búsqueda que existen.

a) Búsqueda secuencial

A este método también se le conoce como búsqueda lineal y consiste en empezar al inicio del conjunto de elementos , e ir a través de ellos hasta encontrar el elemento indicado ó hasta llegar al final de arreglo.

Este es el método de búsqueda más lento, pero si nuestro arreglo se encuentra completamente desordenado es el único que nos podrá ayudar a encontrar el dato que buscamos.

ind <- 1
encontrado <- falso
mientras no encontrado y ind < N haz
	si arreglo[ind] = valor_buscado entonces
		encontrado <- verdadero
	en caso contrario
		ind <- ind +1

b) Búsqueda binaria

Las condiciones que debe cumplir el arreglo para poder usar búsqueda binaria son que el arreglo este ordenado y que se conozca el numero de elementos.

Este método consiste en lo siguiente: comparar el elemento buscado con el elemento situado en la mitad del arreglo, si tenemos suerte y los dos valores coinciden, en ese momento la búsqueda termina. Pero como existe un alto porcentaje de que esto no ocurra, repetiremos los pasos anteriores en la mitad inferior del arreglo si el elemento que buscamos resulto menor que el de la mitad del arreglo, o en la mitad superior si el elemento buscado fue mayor.

La búsqueda termina cuando encontramos el elemento o cuando el tamaño del arreglo a examinar sea cero.

encontrado <- falso
primero <- 1
ultimo <- N
mientras primero <= ultimo y no encontrado haz
	mitad <- (primero + ultimo)/2
	si arreglo[mitad] = valor_buscado entonces
		encntrado <- verdadero
	en caso contrario
		si arreglo[mitad] > valor_buscado entonces
			ultimo <- mitad - 1
		en caso contrario
			primero <- mitad + 1

c) Búsqueda por Hash

La idea principal de este método consiste en aplicar una función que traduce el valor del elemento buscado en un rango de direcciones relativas. Una desventaja importante de este método es que puede ocasionar colisiones.

funcion hash (valor_buscado)
	inicio
		hash <- valor_buscado mod numero_primo
	fin

inicio <- hash (valor)
il <- inicio
encontrado <- falso
repite
	si arreglo[il] = valor entonces
		encontrado <- verdadero
	en caso contrario
		il <- (il +1) mod N
hasta encontrado o il = inicio

Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz