1Resumen de búsquedas Internas

Cristhian Camilo Martínez Rey

John Eddi Malagón González

Juan David Rosero Torres

     Octubre 2020

Universidad Distrital Francisco José de Caldas

Facultad de ingeniería

Bogotá D.C

Ciencias de la computación II
 ii
Abstract

En este documento se presenta un breve resumen acerca de las búsquedas

internas, con el fin de presentar al lector qué es una búsqueda interna, cuáles son los
distintos tipos que existen, y cuál es su uso en las ciencias de la computación; además
de explorar qué es un árbol de búsqueda.

Búsquedas Internas
 iii
Tabla de Contenidos

Capítulo 1 ¿Qué es busqueda interna?..................................................................1

Capítulo 2 Tipos de busqueda binaria...................................................................3
Secuencial o lineal..............................................................................................3
Binaria………………………………………………………………………………....3
Por transformación de claves.............................................................................4
Función hash por modulo................................................................................5
Función hash cuadrado...................................................................................6
Función hash por plegamiento........................................................................6
Función hash por truncamiento.......................................................................7
Reasignación...................................................................................................7
Arreglos anidados............................................................................................7
Encadenamiento..............................................................................................8
Arboles de busqueda..........................................................................................8
Capítulo 3 Resultados y discussion.......................................................................9
Lista de referencias..............................................................................................10

Búsquedas Internas
 Capítulo 1
¿Qué es búsqueda interna?

La búsqueda se considera una de las operaciones más importantes en el

procesamiento de la información. La búsqueda puede ser desarrollada bien por
personal humano, o por programas creados para este fin. Una persona
encargada de la búsqueda de documentos en una empresa puede llegar a tardar
dos o tres minutos para encontrar un archivo específico, bajo la consideración de
que el historial de archivos se encuentre perfectamente organizado y
catalogado; la búsqueda a través de la tecnología, por el contrario, puede
realizarse en pocos segundos y no hay el riesgo de pérdida de documentos por
error humano. (Diaz, 2006)

De esta manera, la búsqueda de información permite recuperar datos

previamente almacenados, de manera que hay dos posibles resultados,
encontrar el archivo, o no hacerlo, es decir, éxito y fracaso, respectivamente. Se
observa entonces que la búsqueda interna es una operación bastante importante
que se desarrolla en los computadores en todos los niveles y con infinidad de
implementaciones distintas. En la operación de búsqueda se usa para la
recuperación de datos que se habían almacenado con anticipación. Esta
operación puede ser de éxito o de fracaso. (Métodos de Búsqueda, n.d.)

Cuando se realiza la búsqueda en una estructura de datos lineal, es decir, en

un array, se puede clasificar como búsqueda interna o externa, según el lugar en
el que se encuentre almacenada la información de interés, bien sea en la
memoria interna o en dispositivos externos.

-          Operaciones de búsqueda interna: Son aquellas que se realizan en la

memoria principal, analizando y procesando todos los datos allí presentes.

Búsquedas Internas
-          Operaciones de búsqueda externa: Son aquellas que se realizan en
diversos dispositivos de almacenamiento, suelen ser de acceso lento.

La complejidad computacional es entonces un factor clave en cualquier

algoritmo de búsqueda u ordenación; también se incluye como esta complejidad
computacional depende del número de datos a procesar. (Tema 8: Algoritmos de
Ordenación y Búsqueda, n.d.)

Los algoritmos de búsqueda generalmente tienen dos objetivos principales,

determinar si el elemento buscado se encuentra en el conjunto de datos donde
se realiza la búsqueda; y de ser así, determinar la posición en la que se
encuentra un elemento. Su volumen es demasiado elevado para trasladarlos
todos a la memoria principal, lo cual fuerza realizar numerosos accesos al
dispositivo de almacenamiento masivo.

Se denomina búsqueda interna cuando todos los elementos se encuentran

en la memoria principal de la computadora; por ejemplo, almacenados en
arreglos, listas ligadas o árboles. Es búsqueda externa si los elementos están en
memoria secundaria; es decir, si hubiera archivos en dispositivos como cintas y
discos magnéticos. (Datos, n.d.)

La búsqueda interna trabaja con elementos que se encuentran almacenados

en la memoria principal de la máquina. Éstos pueden estar en estructuras
estáticas, arreglos o dinámicas, listas ligadas y árboles. Los métodos de
búsqueda interna más importantes son:

-        Secuencial o lineal

-        Binaria

Búsquedas Internas
 -    Por transformación de claves

-     Arboles de búsqueda 

Búsquedas Internas
 Capítulo 2
Tipos de Búsquedas internas

Secuencial o lineal

    Cuando los datos se almacenan en una colección, por ejemplo, en una
lista, se dice que tienen una relación secuencial o lineal. Cada dato se
almacena en una posición relativa a los demás, con esto se puede decir
que al aplicar este tipo de búsqueda se comprueba en serie cada
elemento de la lista hasta que es encontrado el valor objetivo, o hasta que
se hayan comparado todos los datos.

    En términos de tiempo se puede decir que es el peor, y marca como

máximo n comparaciones, donde n será la longitud de la lista. Debido a lo
anterior, la búsqueda lineal o secuencial es práctico aplicar cuando la lista
posee pocos elementos, o cuando se realiza una sola búsqueda en una
lista desordenada. (Datos, n.d.)

    Las ventajas de este método son: la sencillez de implementar, no

requiere que el listado esté ordenado o en algún estado especial. Por el
contrario, las desventajas son: es poco eficiente ya que se debe recorrer
por completo el arreglo, tiempo excesivo de procesamiento en vectores
grandes, en el peor de los casos se requieren de N comparaciones.
(LaBusquedaSecuencial, n.d.)

Binaria

    El algoritmo consiste en reducir el ámbito de búsqueda a mitad de los

elementos, basándose en comparar el elemento a buscar con el elemento
que se encuentra en la mitad del intervalo, con base a esto se tiene que:

Búsquedas Internas
  Si el elemento buscado es menor que el elemento medio,
entonces se sabe que el elemento está en la mitad inferior
del arreglo.
 Si el elemento es mayor es porque el elemento está en la
mitad superior del arreglo.
 Si es igual se finaliza con éxito el algoritmo ya que se habrá
encontrado el elemento.

Este método se puede aplicar tanto a arreglos, vectores, matrices y

árboles binarios de búsqueda. Los requisitos que se tienen son:

 La lista debe estar ordenada de acuerdo a la llave.

 Debe conocerse el número de registros.

Por transformación de claves

     Tanto el método de búsqueda secuencial como binaria tiene un

desempeño (tiempo de búsqueda) proporcional al número de
componentes. Es decir que mientras haya más elementos en el arreglo,
más comparaciones se deben hacer; y aunque el método de búsqueda
binaria es más eficiente que el secuencial, cuenta con la limitación de que
el arreglo debe estar ordenado. Es por esto que se presenta el método de
transformación de claves.

     El método de transformación de claves (también conocido como hash)

permite aumentar la velocidad de búsqueda independiente del número de
elementos del arreglo, sin la necesidad de tener los elementos ordenados
en el arreglo. (Diaz, 2006)

Búsquedas Internas
      Ya que la búsqueda de elementos se optimiza al evitar tener que
recorrer todos los elementos para encontrar el buscado, el método de
transformación de claves logra esto debido a que trabaja utilizando una
función que convierte una clave dada en una dirección dentro del arreglo,
esta función se conoce como función hash (h). (Ruano, 2019) El caso
más trivial se da cuando las claves son números enteros consecutivos.
Sin embargo, se tiene que tener cuidado de que estas claves no sean
extremadamente grandes o sean valores de tipo alfanumérico ya que
para estos casos es cuando se usa una función hash que permita
transformar esos valores en una dirección apropiada. Esta función hash
debe cumplir con las siguientes características:

 Debe ser fácil de calcular

 Debe asignar direcciones diferentes para claves diferentes.

     Es muy importante que se cupla la segunda característica ya que

cuando esto no se cumple, se presenta una colisión que se define como
la asignación de una misma dirección para dos o más claves. (Ruano,
2019) Cuando se presenten estos casos, la función hash elegida deberá
de contar con algún método que genere posiciones alternativas. Es aquí
donde aparece el principal problema de este método ya que no existe
alguna regla escrita que permita determinar la función más apropiada
para un conjunto de claves.

Algunas funciones hash más utilizadas son:

Función hash por módulo

La función hash por módulo o división consiste en tomar el residuo de

la división de la clave entre el número de componentes del arreglo.

Búsquedas Internas
 (Ruano, 2019) Por ejemplo, para el caso de un arreglo de N elementos y
una clave K a buscar. La función hash queda definida así:

H ( K )=( K mod N ) +1 (1)

Es importante que el número N sea un numero primo o un número

divisible por pocos numeros, de modo que, si el tamaño del arreglo no es
un número primo como 100, se debe cambiar por el primo más cercano
(97).

Función hash cuadrado

La función hash cuadrado consiste en elevar al cuadrado la clave y

tomar los dígitos centrales como dirección. El número de dígitos tomar se
encuentra determinado por el rango del índice. (Ruano, 2019) Sea K la
clave del dato a buscar, la función quedaría de la siguiente manera:

H ( K )=¿ (2)

Función hash por plegamiento

La función hash por plegamiento consiste en dividir la clave en partes,

tomando igual número de dígitos, aunque la última pueda tener menos, y
operar con ellas, asignado como dirección los dígitos menos
significativos. La operación entre las partes se puede realizar con sumas
o multiplicaciones según se prefiera. (Ruano, 2019) Siendo K la clave del
dato a buscar, y k formada por los dígitos d1, d2,....dn. La función hash
por plegamiento quedaría así:

H ( K )=dimenSig ¿ (3)

Siendo “digmenSig” el operador para tomar las cifras menos

significativas.
Búsquedas Internas
 Función hash por truncamiento

La función hash por truncamiento consiste en tomar algunos dígitos de

la clave y formar con ellos una dirección. (Ruano, 2019) A Pesar de que
este método es de los más sencillos también es el que ofrece menos
uniformidad en la distribución de las claves. Siendo K la clave del dato a
buscar, y que está formada por los dígitos d1, d2, d3,......dn. La función
hash por truncamiento quedaría de la siguiente forma:

H ( K )=elegirDigitos ( d 1 , d 2 , ….. , d n ) +1 (4)

Para solucionar las posibles colisiones que se presenten al momento

de usar el método de la función hash se presentan algunos métodos que
se clasifican en los siguientes grupos:

Reasignación

     Algunos métodos que trabajan bajo el principio de comparación y

reasignación son:

Prueba lineal: Consiste en detectar la colisión y recorre el arreglo desde

esa posición hasta encontrar una posición vacía. (Diaz, 2006)
Prueba cuadrática: Funciona de manera similar al método anterior, con
la diferencia de que este genera las direcciones alternativas con el
siguiente modelo: (Diaz, 2006)

D+1 , D+ 4 , D+9 , … … , D+i 2 (5)

Arreglos anidados

El método de arreglos anidados consiste en que cada elemento del

arreglo tenga otro arreglo, en el cual se almacenan los elementos que
colisionan. (Ruano, 2019)
Búsquedas Internas
 Encadenamiento

El método de encadenamiento consiste en que cada elemento del

arreglo tenga un apuntador a una lista ligada, la cual se irá generando y
almacenará los valores que colisionan. Cabe resaltar que este el método
más eficiente debido al dinamismo propio de las listas. (Diaz, 2006)

Arboles de búsqueda

     Como ya se sabe, los árboles son una estructura de datos muy dinámica y
versátil al momento de usarla en memoria principal, es por esto que se usa
como método de búsqueda, ya que mientras más variable será el número de
datos a tratar, será más rápida la búsqueda. (Diaz, 2006)

Este método de búsqueda usa una variante de la estructura de los árboles

llamada trie. Es similar a un árbol con N raíces, con la particularidad de que cada
nodo del árbol puede ser nuevamente un trie, y para cumplir su función se
realiza la búsqueda de igual manera que en un árbol binario, evitando así la
búsqueda secuencial. (Diaz, 2006)

Búsquedas Internas
 Capítulo 3
Resultados y discusión.
Como se ha analizado a lo largo del texto, se puede ver como los algoritmos
de búsquedas internas permiten encontrar elementos almacenados en la
memoria principal, y teniendo una serie de algoritmos que funcionaran mejor o
peor dependiendo de la situación que se nos presente, ya sea, en términos de
tiempo o de memoria.

Búsquedas Internas
 Lista de referencias

Tema 8: Algoritmos de ordenación y búsqueda. (n.d.).

http://biolab.uspceu.com/aotero/recursos/docencia/TEMA 8.pdf

Datos, S. D. E. (n.d.). Algoritmos de Búsqueda Interna.

http://academicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_6.pdf

LaBusquedaSecuencial, runestone.academy. (n.d.).

https://runestone.academy/runestone/static/pythoned/SortSearch/LaBusque
daSecuencial.html

Ruano, A. E. (2019). Búsquedas.

https://es.slideshare.net/AlvaroRuano1/bsqueda-secuencial-y-binaria

Diaz, N. (2006). Busqueda de vectores.

http://artemisa.unicauca.edu.co/~nediaz/EDDI/cap02.htm

Métodos de Búsqueda. (n.d.). http://ual.dyndns.org/biblioteca/Estructura de

Datos/Pdf/09 Metodos de busqueda.pdf

Búsquedas Internas