Arreglos unidimensionales y algoritmo de b·squeda binaria

Arreglos Unidimensionales

Los tipos de datos simples tienen como característica común que cada variable representa a un elemento; los tipos de datos estructurados tienen como característica común que un identificador puede representar múltiples datos individuales que pueden ser referenciados de forma independiente.

Los arreglos son una de las estructuras de datos fundamentales. Se caracterizan por almacenarse en memoria de manera continua, bajo un mismo nombre, pero con diferentes índices, para diferenciar la ubicación de cada uno de ellos.

Se utilizan cuando es necesario manipular valores como parte de un conjunto. Se podrían guardar como valores variables simples, pero esto es más complejo de manipular. Por ejemplo, en lugar de tener 1000 variables de tipo cadena de caracteres para guardar los nombres de personas, es más sencillo crear un arreglo de 1000 elementos de tipo cadena de caracteres, ya que toda la información se maneja con el mismo nombre de variable y los elementos se identifican de acuerdo con un subíndice asociado al vector.

Algoritmo de Búsqueda Binaria

1. Algoritmo de búsqueda binaria

Un algoritmo es un conjunto de instrucciones necesarias para realizar una tarea de manera sistemática. Vamos a trabajar con una búsqueda binaria para mostrar cómo un algoritmo puede acelerar la ejecución de un programa o acortar los tiempos para encontrar una solución.

Imagínate hace unos años atrás, buscando a una persona de apellido Martínez en la guía telefónica. Podrías comenzar por la primera página e ir avanzando hasta llegar a la letra M, pero lo más probable es que abras la guía telefónica en una página del medio, porque sabes que los apellidos con M están la mitad de la guía. O imagínate que estás buscando una palabra en eldiccionario que comienza con N. Nuevamente, es probable que comiences la búsqueda cerca del medio.

Ahora, supongamos que estás iniciando una sesión en Facebook. El programa tiene que verificar que tu cuenta existe en el sitio y, para hacerlo, va a buscar tu nombre de usuario en su base de datos. Supongamos que tu nombre de usuario es mpereyra. Facebook podría comenzar desde las A y avanzar hasta encontrar tu usuario, pero tiene más sentido que comience en algún lugar del medio.

Estos son todos problemas de búsqueda, para los cuales podemos utilizar el mismo algoritmo para resolverlos: búsqueda binaria.

La búsqueda binaria es un algoritmo para encontrar un elemento en una lista ordenada de elementos. Funciona al dividir repetidamente a la mitad la lista que podría contener al elemento, hasta reducir las ubicaciones posibles a solo una. Si el elemento buscado se encuentra en la lista, la búsqueda binaria devuelve la posición donde está ubicado. De lo contrario, la búsqueda binaria devuelve nulo.

Adivinar un Número con Búsqueda Binaria

A continuación, veremos un ejemplo práctico sobre cómo funciona la búsqueda binaria. Supongamos que estoy pensando un número en un rango de 1 al 100 y tu objetivo es adivinar este número en el menor número de intentos posible. Con cada selección que hagas te voy a decir si la suposición es muy baja, muy alta o correcta.

Búsqueda simple. Supongamos que empiezas a proponer los números de la siguiente manera: 1, 2, 3, 4 ...

Figura 1: Búsqueda simple

Muy bajo X23 +4 4 100 Muy bajo Fuente: Bhargava, 2016, https://bit.ly/3HI9NMO

En esta búsqueda simple, con cada suposición estás eliminando un solo número. Si mi número elegido fuera 99, ¡podrían requerirse 99 intentos para adivinar el número!Búsqueda binaria. Ahora, utilizaremos la búsqueda binaria como una técnica mejorada, para lo cual vamos a comenzar con el número 50.

Figura 2: Búsqueda binaria

Muy bajo 50 5 51 52 53 Todos estos números son muy bajos Fuente: Bhargava, 2016, https://bit.ly/3HI9NMO

Aunque todavía es demasiado bajo, hemos eliminado la mitad de los números de la lista y ya sabes que debes descartar los números del 1 al 50. El próximo número propuesto será 75.

Figura 3: Búsqueda binaria

Muy alto 75 Fuente: Bhargava, 2016, https://bit.ly/3HI9NMO

En este caso, el número es demasiado alto, pero nuevamente hemos eliminado la mitad de los números restantes. Con esta búsqueda binaria, considerando el número del medio, se eliminan la mitad de los números restantes con cada intento. El siguiente número seleccionado será 63 (mitad de la lista entre 50 y 75). Así, sucesivamente, siempre dividiendo a la mitad la lista que podría contener al elemento.

Figura 4: Búsqueda binaria

Muy alto 63 57 YES! -> :01 Fuente: Bhargava, 2016, https://bit.ly/3HI9NMO

Esta es la búsqueda binaria y acabas de aprender tu primer algoritmo. Cualquiera que sea el número pensado, puedes adivinarlo en un máximo de siete intentos.

Figura 5: Algoritmo

100 ITEMS 7 50 25 > 13 77472 7 intentos Fuente: Bhargava, 2016, https://bit.ly/3HI9NMO

Búsqueda de una Palabra en el Diccionario

Volvamos al ejemplo de la búsqueda de una palabra en el diccionario que tiene en total 240 000 palabras ordenadas alfabéticamente.

La búsqueda simple podría tomar 240 000 intentos, si la palabra que se está buscando es la última. Si utilizamos una búsqueda binaria, con cada intento eliminamos la mitad de las palabras incorrectas hasta quedarnos con la última, lo que nos reduce la cantidad de pasos máximos a 18.

Figura 6: Búsqueda binaria

240 K T 12ØK 6ØK 3ØK 1 15K 7.5K > 3750 59 118 235 4 469 938 - 1875 30 -> 15 -> 8 4 > 2 1 18 intentos Fuente: Bhargava, 2016, https://bit.ly/3HI9NMO

En general, para cualquier lista de n elementos, en el peor de los casos, la búsqueda binaria tomará log2 n pasos para ejecutarse, mientras que la búsqueda simple tomará n pasos.

Para recordar logaritmos, puedes recurrir a la potenciación. Para calcular el log10 100, puedes preguntarte cuántas veces debes multiplicar 10 para obtener 100. La respuesta es 2, ya que 10 x 10 = 100.

Figura 7: Potenciación

102=100 => log,10$ = 2 2' =8 + 10g28-3 2ª = 16 - log2 16=4 2º = 32 109.32=5 Fuente: Bhargava, 2016, https://bit.ly/3HI9NMO

Caso de Estudio: Lista de Productos

Caso lectura 1: lista de productos

Los arreglos son una estructura de datos fundamental, ya que representa un grupo de elementos relacionados que tienen el mismo nombre y tipo de dato. Para poder acceder a los diferentes valores, se utiliza un índice. Los arreglos son extremadamente útiles en programación, ya que nos permiten acceder a grandes cantidades de datos de manera sencilla.

Calipso es una empresa que se dedica a la venta de electrodomésticos, nacida en la ciudad de Juan José Castelli, provincia de Chaco. Comenzó sus actividades en el año 1991 y tuvo una gran expansión a partir de 2003, que le permitió abrir sucursales en muchas provincias del país. En este contexto, te contrata para que puedas desarrollar un sistema de gestión de stock y ventas. Vamos a trabajar con este caso a lo largo de módulo y, en esta primera lectura, tu objetivo es comenzar con un MVP (mínimo producto viable). Para ello, el objetivo es implementar un algoritmo que permita el ingreso de 5 electrodomésticos y los almacene en un arreglo unidimensional. Para validar la carga, este algoritmo debe dar la posibilidad de que el usuario confirme si desea listar los productos, en cuyo caso es necesario recorrer el arreglo y mostrar los valores cargados.

Tipos de Datos y Abstracción

Tipos de datos y abstracción

La abstracción es la capacidad de aislar información de diseño y ejecución en el interior para presentar solo los detalles relevantes de un elemento, que podría ser un objeto en POO.

Es importante diferenciar algunos conceptos que nos van a permitir entender la importancia del manejo de datos en cualquier lenguaje de programación.

Tipo de datos: son los valores que puede tomar la variable, junto a las operaciones elementales que nos permiten trabajar con ellos. Por ejemplo, en los números enteros se puede aplicar operaciones aritméticas.

Estructura de datos: se caracterizan por el tipo de datos de los elementos que la componen, las relaciones entre ellos y las operaciones permitidas sobre la estructura. Las operaciones típicas suelen ser buscar y acceder a los elementos, insertar o borrar elementos, modificar las relaciones entre los elementos, etc.

Tipo de dato abstracto (TDA): es tipo de dato creado por el programador que encapsula una estructura de datos para almacenar la información y presenta un conjunto de operaciones como comportamiento, pero manteniendo oculta su implementación. Es decir, se define qué debe hacer y no el cómo.

En cada lenguaje de programación, los TDA se implementan utilizando diferentes metodologías. Por ejemplo, en el lenguaje C, se implementan principalmente con estructuras (structure) y en Java, mediante clases (class).

Estructura de Datos

Estructura de datos

Una estructura de datos es una colección de datos que se caracteriza por el tipo de datos de los elementos que la componen, las relaciones entre ellos y las operaciones permitidas. Es decir que pueden existir una gran cantidad de estructuras de datos.

Lo que caracteriza a una estructura de datos es el tipo de problema que resuelve. En algunos casos, es probable que necesitemos una estructura muy simple que nos permita almacenar 5 números enteros a los cuales podemos acceder mediante un índice. En otros casos, podemos requerir N números enteros, pero que se ordenen de forma ascendente con cada nuevo valor introducido, y se va a requerir una estructura mucho más flexible.

Las estructuras de datos son muy importantes en los sistemas de computadora. Los tipos de datos más frecuentes utilizados en los diferentes lenguajes de programación son los siguientes.

Figura 8: Tipos de datos

Datos simples Datos estructurados Estándar Estáticos · arrays (vectores/matrices) · entero (integer) · real (real) caracter (char) · lógico (boolean) · registros (record) archivos (files) conjuntos (set) · cadenas (string) Definido por el programador Dinámicos · listas (pilas/colas) · listas enlazadas · enumeraciones (enumerated) subrango (subrange) · árboles · grafos Fuente: elaboración propia

Las estructuras de datos son útiles porque, cuando tenemos los datos organizados, es más simple trabajar con ellos y procesarlos para obtener información. Existen para ayudarnos en la compleja tarea de resolver problemas en programación, independientemente del lenguaje utilizado.

Con el propósito de procesar los datos para obtener información, debemos almacenarlos en memoria y posteriormente recuperarlos. "Cuando creamos una variable estamos almacenando un valor en memoria. Y al indicar el tipo de datos, estamos especificando cómo se codifican y qué cantidad de bits se destinan para almacenar esos datos" (Blanco Rivero, s.f., https://bit.ly/3VdcV2M).

De acuerdo con la forma en la que los datos se organizan, se clasifican en datos simples y datos estructurados.

Figura 9: Tipos de datos simples y estructurados

Identificador Identificador Dato simple Dato estructurado Fuente: elaboración propia

Tipos de Datos Simples

La principal característica de los tipos de datos simples es que hacen referencia a un único valor a la vez. Su contenido se trata como una unidad que no puede separarse en partes más elementales. En este grupo de datos se encuentran números enteros, números reales, caracteres y booleanos. (Cairó y Guardati, 2006, p. 15)

En algunos lenguajes de programación existen otros tipos de datos simples, como los enumerados y subrangos. En los tipos enumerados se especifican los valores de sus elementos: días de la semana, estaciones del año, etc. Un subrango es un subconjunto de un tipo