Búsqueda Lineal:

Este tipo de búsqueda permite buscar registros dentro de un vector, el cual no requiere estar ordenado.

El vector se recorre desde el primer elemento hasta el último y solo termina la búsqueda cuando se ha encontrado el registro, o cuando se recorre el vector por completo (no se encuentra el registro en el vector).

Un ejemplo de este tipo de búsqueda seria buscar un elemento del vector, en este caso buscaremos el siguiente elemento:

rojo

Acá tenemos nuestro vector

vector

Como pueden ver el vector no está ordenado, ahora veremos lo que hace la búsqueda lineal para encontrar el elemento requerido.

rojo       ¿8 es igual a 3?    NO                                                 

1   

rojo     ¿8 es igual a 4?    NO

2

rojo      ¿ 8 es igual a 8?  SI

3  Fin de la búsqueda. 

Búsqueda Binaria:

Para poder usar este tipo de búsqueda el vector debe de estar ordenado, este método permite trabajar con vectores de gran tamaño reduciendo los tiempos de búsquedas al comparar el elemento que se quiere encontrar con el elemento central del vector.

¿Porqué tarda menos en buscar un elemento en un vector?

Esto se debe a que no trabaja con todos los elementos del vector, lo que hace es verificar si el elemento a buscar es igual al elemento central (fin de búsqueda), menor al elemento central (se trabaja con el subvector izquierdo) o mayor al elemento central (se trabaja con el subvector derecho).

Permitiendo que cada vez que realice una comparación con un elemento central se cree un subconjunto más pequeño hasta encontrar el elemento deseado.

Ejemplo:

Buscar un elemento dentro de una lista ordenada.

Elemento:

32

Lista ordenada

21

Al comparar el elemento a buscar con el elemento central de la lista ordenada, hará que la lista se vaya dividiendo por la mitad hasta encontrar el registro/elemento.

32   ¿32 es igual a 8? NO

¿32 es mayor 8 ? SI (el elemento se encuentra en el subvector derecho)

division 1

Ahora solo se trabajará con ese subvector

q

32  ¿32 es igual a 32? SI

fin Fin de búsqueda.

Cuadro Comparativo

Cuadro Comparativo

Descargar Cuadro Comparativo en PDF

Adjunto un PowerPoint con las funciones hash que aparecen en el cuadro comparativo (truncamiento, plegamiento, mitad del cuadrado, etc.).

Funciones Hash