Algoritmos y estructuras de
datos
VECTORES
Luis E. Seijas
Enero, 2024
Contenido
1. Introducción
2. Estructura interna de un vector
3. Creación de un vector
4. Recorridos
5. Búsquedas
Arreglos o arrays unidimensionales
¿ Por qué son importantes los arreglos unidimensionales en
las ciencias de la computación?
Arreglos o arrays unidimensionales estáticos
un vector es un contenedor que nos permite almacenar y acceder a datos.
Pero a diferencia de otros contenedores de datos más complejos, como las
listas enlazadas o los árboles, un vector es una estructura unidimensional y
estática.
• Unidimensional significa que esta estructura contiene sólo una fila de datos
• Cada dato en el vector tiene un índice
• Es posible acceder directamente a un valor en el vector si conocemos su
índice
• Que sea estático significa que su tamaño se determina al momento de su
creación
Arreglos o arrays unidimensionales estáticos
Representación en memoria de un vector
Creación de un array unidimensional
Operaciones con vectores
Un arreglo cómo una estructura de datos sólo admite dos operaciones:
1. Almacenamiento de valores (escribir)
2. Recuperación de valores (leer)
Operaciones con vectores
Operaciones con vectores
Recorridos de un vector
Recorrido de un
vector estático
de tamaño 5
con un bucle
while
Recorridos de un vector
Recorrido de un
vector estático
de tamaño 5
con un bucle do-
while
Recorridos de un vector
Recorrido de un
vector estático
de tamaño 5
con un bucle do-
while
Recorridos de un vector
Recorrido de un
vector estático
de tamaño 5
con un bucle for
Búsquedas de elementos en un array 1D
Búsqueda
Lineal Binaria
Útil cuando los datos están
La complejidad de tiempo de la
La complejidad de tiempo de la Útil cuando los datos están ordenados y cuando tenemos un
búsqueda binaria en el peor
búsqueda lineal en el peor caso desordenados o cuando gran número de elementos a
caso es O(log n), donde n es el
es O(n), donde n es el número tenemos un pequeño número buscar. Es una opción eficiente,
número de elementos en el
de elementos en el arreglo. de elementos a buscar pero requiere que los datos
arreglo.
estén ordenados
Búsqueda lineal (Algoritmo)
1. Comienza en el primer elemento del arreglo.
2. Compara el elemento actual con el valor que estás buscando.
3. Si el elemento actual es igual al valor buscado, entonces has
encontrado el valor y puedes terminar la búsqueda.
4. Si el elemento actual no es igual al valor buscado, pasa al siguiente
elemento del arreglo.
5. Repite los pasos 2-4 hasta que encuentres el valor buscado o hasta
que hayas comparado todos los elementos del arreglo.
6. Si has comparado todos los elementos del arreglo y aún no has
encontrado el valor, entonces el valor no se encuentra en el arreglo.
Búsqueda lineal (Algoritmo)
Búsqueda binaria (Algoritmo)
1. Asegúrate que el arreglo esté ordenado
2. Comienza con dos índices, ‘low’ y ‘high’, que representan los extremos del
subarreglo que se está examinando. En el primer paso ‘low’ es 0 y ‘high’ es el
último índice del arreglo.
3. Mientras ‘low’ sea menor que ‘high’:
3.1 Cálcula el índice ‘mid’ como ‘(low + high) / 2’
3.2 Si el valor en el índice ‘mid’ es igual al valor que estas buscando, entonces has
encontrado el valor y la búsqueda termina.
3.3 Si el valor en el índice ‘mid’ es menor que el valor que estas buscando,
entonces actualiza ‘low’ para ser ‘mid + 1’. Es decir, limita la búsqueda a la
segunda mitad del sub arreglo
3.4 Si el valor en el índice ‘mid’ es mayor que el valor que estas buscando,
entonces actualiza ‘high’ para ser ‘mid - 1’. Es decir, limita la búsqueda a la
primera mitad del sub arreglo
4. Si ‘low’ se hace mayor que ‘high’ y aun no se ha encontrado el valor, entonces el
valor no está en el arreglo.
Búsqueda lineal
(Ejemplo de
implementación)
Búsqueda binaria (Algoritmo)
Búsqueda binaria
(Ejemplo de
implementación)
Conclusión
•Los arreglos unidimensionales estáticos, o vectores, son una estructura de datos esencial
en la programación, que almacena elementos del mismo tipo en una ubicación de
memoria contigua.
•Los vectores tienen una longitud fija que se define en el momento de su creación. Cada
elemento en el vector puede ser accedido directamente a través de su índice.
•Hemos aprendido a declarar, inicializar y recorrer vectores en varios lenguajes de
programación.
Conclusión
•Discutimos dos métodos comunes de búsqueda en un vector: búsqueda lineal y
búsqueda binaria. La búsqueda lineal es simple pero puede ser lenta para vectores
grandes, mientras que la búsqueda binaria es rápida pero requiere que el vector esté
ordenado.
•A través de los ejercicios, practicamos la creación, recorrido y búsqueda en vectores, lo
que nos proporcionó una comprensión práctica de estos conceptos.
