INSTITUTO TECNOLÓGICO SUPERIOR DE TIERRA BLANCA

ING. EN SISTEMAS
COMPUTACIONALES
MATERIA:
Estructura de datos.

ACTIVIDAD:
Investigación

INTEGRANTES:
Omar Illescas Escobedo
218N0046
Emmanuel Hernández
Vásquez 218N0044
Miguel Gutiérrez Sánchez
218N0043
Elihú Rangel Martínez
218N0058

ASESOR:
Eva Mora Colorado.

FECHA DE ENTREGA:
8/12/2022
Índice
Introducción.......................................................................................................................................2
6.1 Búsqueda secuencial....................................................................................................................3
6.2 Búsqueda binaria..........................................................................................................................5
6.3 Búsqueda por funciones de HASH................................................................................................7
Funciones en hash más comunes............................................................................................8
Conclusión........................................................................................................................................9
Bibliografía.......................................................................................................................................10

1
 Introducción.

Dentro del contenido se presenta los conceptos de algoritmos de búsquedas,

además de los tipos de búsqueda, dichos algoritmos se dan a conocer con sus
aspectos específicos, sus ventajas y desventajas.
Se da a conocer el como utilizar tales algoritmos respectivamente de algún
conjunto de elementos, así al implementarse no se darán consecuencias
negativas.
Para comenzar se proporciona que una búsqueda consiste en solucionar un
problema de membresía de un elemento determinado en un conjunto finito de
elementos. Mientras que un algoritmo de búsqueda está diseñado para localizar
un elemento concreto dentro de una estructura de datos.

2
 6.1 Búsqueda secuencial

La búsqueda secuencial, también se le conoce como búsqueda lineal. 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 arreglo 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 arreglo.
Este método recorre el arreglo o vector elemento a elemento e ir comparando con
el valor buscado (clave). Se empieza con la primera casilla del vector y se observa
una casilla tras otra hasta que se encuentre el elemento buscado o se han visto
todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición
del elemento buscado o cero. Dado que el vector o arreglo no está en ningún
orden en particular, existe la misma probabilidad de que el valor se encuentra ya
se en el primer elemento, como en el último. Por lo tanto, en promedio, el
programa tendrá que comparar el valor buscado con la mitad de los elementos del
vector.
El proceso termina cuando o bien encontramos el elemento o bien se alcanza el
final del vector.
El método de búsqueda lineal funciona bien con arreglos pequeños o para
arreglos no ordenados.

3
A continuación, se muestra el pseudocódigo del algoritmo: [cita requerida]
Datos de entrada:
  vec: vector en el que se desea buscar el dato
  tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1
inclusive.
  dato: elemento que se quiere buscar.
Variables
  pos: posición actual en el arreglo
pos = 0
Mientras pos < tam:
  Si vec[pos] == dato devolver verdadero y/o pos, de lo contrario:
  pos = pos + 1
Fin (Mientras)
Devolver falso,

Ventajas:
 Es un método sumamente simple que resulta útil cuando se tiene un
conjunto de datos pequeños (Hasta aproximadamente 500 elementos)
 Es fácil adaptar la búsqueda secuencial para que utilice una lista enlazada
ordenada, lo que hace la búsqueda más eficaz.
 Si los datos buscados no están en orden es el único método que puede
emplearse para hacer dichas búsquedas.
 
Desventajas:
 Este método tiende hacer muy lento.
 Si los valores de la clave no son únicos, para encontrar todos los elementos
con una clave particular, se requiere buscar en todo el arreglo, lo que hace
el proceso muy largo.

4
 6.2 Búsqueda binaria.

La búsqueda binaria, también conocida como búsqueda de medio

intervalo, búsqueda logarítmica, o corte binario, es un algoritmo de búsqueda que
encuentra la posición de un valor objetivo dentro de una matriz ordenada. La
búsqueda binaria compara el valor objetivo con el elemento medio de la matriz. Si
no son iguales, se elimina la mitad en la que el objetivo no puede estar y la
búsqueda continua en la mitad restante, tomando nuevamente el elemento del
medio para compararlo con el valor objetivo y repitiendo esto hasta encontrar el
valor objetivo. Si la búsqueda termina con la mitad restante vacía, el objetivo no
está en la matriz.
A diferencia de la búsqueda secuencial, este tipo de búsqueda se usa cuando ya
tenemos un arreglo ordenado, sin importar ni el tipo de ordenamiento usado, ni si
este fue ordenado de forma ascendente o descendente, lo que hace este
algoritmo es parte el arreglo a la mitad y empieza a buscar, si fue encontrado se
encenderá una bandera, de lo contrario pregunta si se es menor o mayor para irse
hacia arriba o abajo del arreglo.
El proceso comienza comparando el elemento central del arreglo con el elemento
buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento
buscado será mayor o menor en sentido estricto que el elemento central del
arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en
el subrayar superior, si el elemento buscado es menor que el contenido de la
casilla central, se debe cambiar el segmento a considerar al segmento que está a
la izquierda de tal sitio central.

5
Este método se puede aplicar tanto a datos en listas lineales como
en árboles binarios de búsqueda. Los pre – requisitos para la búsqueda binaria
son:
 La lista debe estar ordenada, en un orden especifico de acuerdo al valor de
la clave.
 Debe conocerse el número de elementos.
 Si el conjunto de elementos es grande, el tiempo de búsqueda se puede
reducir utilizando el siguiente algoritmo de tipo divide y vencerás:
 Se divide el elemento en dos partes.
 Se determina la parte que debe contener la clave buscada.
 Se repite el proceso en esa parte.
Una forma razonable de dividir el conjunto de elementos es mantener los
elementos ordenados y después utilizar los índices del arreglo ordenado para
determinar la parte del arreglo sobre la que se va a trabajar.
El rendimiento de la búsqueda binaria puede ser analizada reduciendo el algoritmo
a un árbol binario de búsqueda, donde la raíz es el elemento en el medio del
arreglo, el elemento en el medio de la primera parte del arreglo es el hijo izquierdo
de la raíz y el elemento en el medio de la segunda parte es el hijo derecho de la
raíz. El resto del árbol se construye de forma similar. Este modelo representa a la
búsqueda binaria, comenzando desde la raíz, el subárbol izquierdo o derecho son
recorridos de acuerdo a si el valor buscado es menor o mayor que el valor
presente en el nodo actual, representando la eliminación sucesiva de los
elementos.

Pseudocódigo de búsqueda Binaria

6
Ventajas:
 Se puede aplicar tanto a datos en listas lineales como en árboles binarios
de búsqueda.
 Es el método más eficiente para encontrar elementos en un arreglo
ordenado.
Desventajas:
 Este método funciona solamente con arreglos ordenados, por lo cual, si nos
encontramos con arreglos que no están en orden, este método, no nos
ayudaría en nada.

6.3 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.

La idea básica de este método consiste en aplicar una función que traduce un
conjunto de posibles valores llave en un rango de direcciones relativas.
Hash se refiere a una función o método para generar claves o llaves que
representen de manera casi unívoca a un registro, archivo, documentó, etc.

7
Un problema potencial encontrado en este proceso, es que tal función no puede
ser uno a uno; las direcciones calculadas pueden no ser todas únicas, cuando
R(k1 )= R(k2)Pero K1 diferente de K2 decimos que hay una colisión.
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 más 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 más 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
contará con algún método que genere posiciones alternativas.

Funciones en hash más comunes.

Residuo de la división.
Dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo
de la división como dirección relativa para el registro (dirección = llave módulo
divisor).

Medio del cuadrado.

La llave es elevada al cuadrado, después algunos dígitos específicos se extraen
de la mitad del resultado para constituir la dirección relativa.
8
Pliegue.
En esta técnica el valor de la llave es particionada en varias partes, cada una de
las cuales (excepto la última) tiene el mismo número de dígitos que tiene la
dirección relativa objetivo. Estas particiones son después plegadas una sobre otra
y sumadas. El resultado, es la dirección relativa.
Ventajas:
 El tiempo de búsqueda es independiente del número 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.

Conclusión
Se comprende el como tales algoritmos de búsqueda tienden a lograr encontrar
algún elemento que se requiere, el cual se encuentra dentro de un conjunto de
elementos (arreglo), sin embargo, hay que tener en claro cada complejidad que
llega a tener los algoritmos, por ejemplo, mediante el proceso que se lleva durante
la búsqueda.
Por lo cual tienen su propio proceso los cuales son de correcta implementación de
acuerdo a las características de el arreglo, de los tamaños, cantidad, tiempo entre
otros aspectos que se deben tener en cuenta para la máxima obtención de
elementos.

9
 Bibliografía
Acosta, J. A. (20 de Octubre de 2016). Obtenido de
https://es.slideshare.net/JosAntonioSandovalAc/estructura-de-datos-unidad-
6-metodos-de-busqueda
Estructura de Datos -Tema 6: Métodos de Búsqueda. (4 de Diciembre de 2018).
Obtenido de http://eddt6.blogspot.com/2018/12/busqueda-por-funciones-de-
hash.html
Garcia, O. (s.f.). Blogspot. Obtenido de
http://estructuradedatos10110795.blogspot.com/p/metodo-de-busqueda-
hash.html
Gutiérrez, G. M. (28 de 5 de 2013). TPM. Obtenido de
https://itslr.edu.mx/archivos2013/TPM/temas/s3u6.html#:~:text=Consiste
%20en%20buscar%20el%20elemento,que%20se%20llegue%20al%20final.
HMong. (s.f.). Obtenido de https://hmong.es/wiki/Binary_search
PUERTOS DE COMUNICACION AL COMPUTADOR. (11 de 2007). Obtenido de
https://uneginginf05.es.tl/M-e2-todo-de-Busqueda-Secuencial-y-Binaria.htm
Vicente, J. (21 de Abril de 2004). ALGORITMOS DE BUSQUEDA Y
ORDENACIÓN . Obtenido de
https://www.infor.uva.es/~jvalvarez/docencia/pII%20antiguo/tema6.pdf
Wikipedia . (17 de Noviembre de 2022). Búsqueda binaria. Obtenido de
https://es.wikipedia.org/wiki/B%C3%BAsqueda_binaria

10