03 · Arreglos y búsqueda lineal
Aprender a programar · Ruta de Aprendizaje
Antes de empezar. Variables, ciclos y entrada/salida: 00 - Programar desde cero y 01 - Tu primer programa.
🎯 Objetivos
Al terminar este módulo sabes:
- Guardar y recorrer secuencias con
vector. - Calcular máximos, mínimos, sumas y conteos en una pasada.
- Buscar un valor y cortar apenas lo encuentras.
📖 La lección
El vector: tu estructura de cabecera
Un vector guarda una secuencia bajo un mismo nombre. El índice elige una
casilla y permite recorrerlas sin crear una variable por dato.
vector<int> a(n) crea n enteros inicialmente iguales a cero; luego la
lectura reemplaza esos valores. Suponemos n >= 0.
int n;
cin >> n;
vector<int> a(n); // n enteros, posiciones 0 .. n-1
for (int i = 0; i < n; i++) cin >> a[i];
cout << a.size() << "\n"; // cantidad de elementos: nCon entrada 5 seguida de 7 3 9 2 5, se guardan cinco números y se imprime 5. El dibujo muestra esas cinco casillas.
Si el diagrama no cabe, deslízalo horizontalmente.
Las posiciones parten en 0. En un vector de tamaño n, son 0..n-1:
leer a[n] está fuera del vector y tiene comportamiento indefinido.
Podemos agregar un elemento después de leer el vector:
// supone: vector<int> a; // el vector ya leído
a.push_back(42);
cout << a.size() << " " << a.front() << " " << a.back() << "\n";Ahora el ejemplo queda {7,3,9,2,5,42} e imprime 6 7 42.
Después de push_back(42) el tamaño pasa a n+1 y esa
nueva posición a[n] sí existe. La regla general es usar índices menores
que a.size(). front() y back() requieren que el vector no esté vacío;
en este ejemplo el push_back garantiza al menos un elemento.
(Todas sus operaciones y sus costos, en vector (arreglo dinámico).)
El patrón acumulador
El ejemplo de máximo supone n ≥ 1: un arreglo vacío no tiene máximo.
Muchos problemas de arreglos se resuelven recorriendo una vez y manteniendo
un resumen de lo leído: el máximo, una suma o un conteo. El resumen cambia
según la pregunta; no necesitamos recordar otra vez todas las comparaciones.
Por ejemplo, para devolver el máximo con su posición, guardamos en mejor
un índice, no el valor máximo. Empezamos en 0 porque el primer elemento
es el mayor de los que hemos visto hasta ese momento:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int mejor = 0; // posición del máximo visto hasta ahora
for (int i = 1; i < n; i++)
if (a[i] > a[mejor]) mejor = i;
cout << "maximo " << a[mejor] << " en posicion " << mejor << "\n";
return 0;
}Sigue la traza con a = {3, 9, 2, 7} — mejor parte en 0 y solo cambia cuando
aparece algo estrictamente mayor:
| i | a[i] | a[mejor] hasta ahora | ¿a[i] > a[mejor]? | mejor después |
|---|---|---|---|---|
| 1 | 9 | 3 | sí | 1 |
| 2 | 2 | 9 | no | 1 |
| 3 | 7 | 9 | no | 1 |
Respuesta: máximo 9 en la posición 1. Fíjate en que si hubiera dos 9, ganaría
el primero (el > estricto no cambia mejor ante un empate); con >=
ganaría el último. Esa decisión aparece en enunciados reales (“en caso de
empate, el de menor índice”).
Variantes del mismo patrón: contar cuántos cumplen algo (if (...) cuenta++),
sumar (suma += a[i], en long long si puede crecer), comparar vecinos
(a[i] con a[i-1]: rachas, repetidos adyacentes).
Búsqueda lineal (y el arte de cortar)
Tenemos a = {3, 9, 2, 7, 2} y queremos la posición de la primera
aparición de 2. El arreglo no está ordenado: ver un 9 no nos dice nada
sobre los valores que vienen después. La estrategia directa es mirar las
casillas de izquierda a derecha, comparando cada valor con lo que buscamos.
Eso es una búsqueda lineal.
Es importante separar dos datos: el valor buscado es 2; su posición también será 2 en este ejemplo, pero no tienen por qué coincidir. Si buscáramos 9, la respuesta sería la posición 1. Los índices empiezan en cero.
Si el diagrama no cabe, deslízalo horizontalmente.
En el dibujo, las dos primeras comparaciones fallan. La tercera encuentra un 2. Como ya comprobamos que a su izquierda no había ninguno, sabemos que es el primero y podemos detenernos. El segundo 2, en la posición 4, no cambia esa respuesta.
Convertir la idea en código
pos guarda la respuesta. Parte en −1, un valor que no puede ser un índice
válido: significa «todavía no lo encontré». En cada vuelta, i indica la
casilla que estamos revisando. El siguiente bloque va dentro de main,
después de leer el vector y el valor buscado; n debe ser el tamaño de a.
// supone: int n, x; vector<int> a; // n y a leídos como arriba; x es lo que buscas
int pos = -1; // -1 = "no está"
for (int i = 0; i < n; i++) {
if (a[i] == x) { pos = i; break; } // ¡corta apenas lo encuentra!
}
cout << pos << "\n";Con el mismo arreglo, la ejecución para x = 2 es:
Posición i | Valor a[i] | ¿Es 2? | Qué ocurre |
|---|---|---|---|
| 0 | 3 | no | pos sigue en −1; avanzamos |
| 1 | 9 | no | pos sigue en −1; avanzamos |
| 2 | 2 | sí | guardamos pos = 2 y salimos del ciclo |
| 3 y 4 | no se leen | — | la respuesta ya está decidida |
break sale del ciclo; luego se ejecuta el cout, que imprime 2.
Si buscáramos 8, ninguna comparación acertaría: revisaríamos las cinco
casillas y el programa imprimiría −1. Solo al terminar ese recorrido
podemos afirmar que no está. Si n = 0, el ciclo no entra y también imprime −1.
La pregunta decide cuándo detenerse
Para el mismo arreglo y el valor 2:
| Pregunta | Respuesta | Qué debemos conservar y cuándo terminar |
|---|---|---|
| ¿Está? | sí | basta el primer acierto |
| ¿Dónde aparece por primera vez? | posición 2 | guardar el índice y cortar |
| ¿Dónde aparece por última vez? | posición 4 | reemplazar el índice en cada acierto y seguir |
| ¿Cuántas veces aparece? | 2 veces | incrementar un contador en cada acierto y seguir |
Si quitamos el break del código, pos se reemplaza en la posición 4:
el programa pasa a resolver la última aparición. Si queremos un conteo,
no basta guardar una posición: necesitamos un contador que parta en cero.
En el mejor caso acertamos en la primera casilla: una comparación. En el
peor caso revisamos las n, porque el valor está al final o no aparece:
tiempo proporcional a n (lo escribiremos O(n) en el módulo 07). Solo añadimos i y pos: una cantidad fija de memoria adicional (O(1)), aparte
del vector que ya teníamos. El corte ahorra trabajo en algunos casos, pero
no cambia el peor caso.
En el módulo 08 podremos descartar grupos completos si el arreglo está ordenado. Aquí, sin esa información, cualquier casilla sin revisar todavía podría contener el valor.
¿Cuántos elementos caben?
El límite del juez es para todo el programa. Estima primero
cantidad de elementos × sizeof(tipo). En los entornos habituales de
competencia, un int ocupa 4 bytes y un long long, 8; sizeof permite
consultarlo en C++. Aquí MB significa un millón de bytes, aproximadamente.
| Datos guardados | Memoria de los elementos |
|---|---|
Un millón de int | 4 MB |
Un millón de long long | 8 MB |
Mil millones de int | 4 GB: no cabe en un límite de 256 MB |
También cuentan otros vectores, copias y memoria del programa. Deja margen: el almacenamiento reservado puede ser mayor que la cantidad de elementos. Si solo necesitas sumar los datos mientras los lees, basta un acumulador; no necesitas conservar el vector completo.
Tamaño y capacidad son distintos. vector<int> v(5) crea cinco ceros;
v.resize(8) lo amplía a ocho elementos, agregando tres ceros. En cambio,
v.reserve(8) solo reserva espacio para crecer: no cambia v.size() ni
permite usar índices nuevos. Sobre un vector vacío, después de reserve(8)
sigue siendo inválido escribir v[0]; usa push_back o crea los elementos
con resize.
En el dibujo suponemos una capacidad de ocho. La capacidad exacta depende de cómo creció el vector: reservar ocho garantiza al menos ocho.
Si el diagrama no cabe, deslízalo horizontalmente.
El número de datos tampoco es su valor máximo. Para contar cien códigos entre 0 y mil millones, un vector de frecuencias por código necesitaría más de mil millones de casillas. En 06 - Conjuntos, mapas y pares verás cómo guardar solamente los códigos que aparecen.
Comprobar la decisión
Llegan un millón de enteros y solo se pide su máximo. Puedes conservar únicamente el mejor valor leído: memoria constante. Si luego debes imprimirlos en orden inverso, sí necesitas conservarlos: unos 4 MB en un vector de
int, además del resto del programa.
🏋️ Práctica
Práctica directa: La primera aparición
Lee n (0 a 100), sus n enteros y x. Imprime la primera posición de x desde cero, o −1. Entrada: 4 / 3 9 2 7 / 2. Salida: 2.
En los ejemplos de entrada y salida, / separa líneas; no se escribe en el archivo.
Idea para comprobar tu solución
Inicia pos en −1 y cambia al primer acierto. Si x es 8, la salida debe ser −1; con n=0, también.
Variación: Elegir qué conservar
Llegan n enteros (1 ≤ n ≤ 100000). Imprime el mayor y cuántas veces aparece, sin conservar todos los datos. Para 6 / -4 -2 -2 -9 -2 -4, la salida es -2 3.
Una pista, si la necesitas
¿Qué ocurre con el contador cuando aparece un máximo nuevo? ¿Y cuando empata?
Contrastar el razonamiento
Al encontrar un máximo nuevo, el contador vuelve a 1; ante un empate aumenta. Inicializa con el primer dato. Una entrada de un solo dato tiene frecuencia 1.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Problemas OCI reales, en español (cada nota trae el link a su mirror):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | Rey De Los Piratas | Regional 2023 | el mejor con desempate, en una pasada |
| 2 | Llaves | Regional 2020 | recorrer con condición y contador |
| 3 | Tormenta China | Regional 2021 | el segundo menor distinto (n ≤ 10⁶) |
| 4 | Secuencia de ADN | Regional 2019 | ventanas de tamaño 3 |
| 5 | ⭐ Carta de navegación | Nacional 2025 | doble pasada sobre un arreglo circular |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | In Search of an Easy Problem (1030A) | ★ (800) | ¿hay algún 1? — búsqueda con corte |
| 2 | Stones on the Table (266A) | ★ (800) | comparar vecinos |
| 3 | Vasya the Hipster (581A) | ★ (800) | mínimos y aritmética |
| 4 | Kefa and First Steps (580A) | ★★ (900) | racha creciente más larga |
| 5 | ⭐ Favorite Sequence (1462A) | ★★ (800) | dos índices desde los extremos |
Un ejemplo para pensar
En el arreglo {-8, -3, -5}, alguien busca el máximo iniciando su valor
en cero. Otra persona guarda la posición del primer elemento y compara
los siguientes con él. ¿Por qué solo la segunda idea funciona aquí?
Compara el código y predice su salida antes de ejecutarlo:
vector<int> a = {-8, -3, -5};
int maximo = 0; // A: candidato inicial externo al arreglo.
for (int i = 0; i < 3; i++)
if (a[i] > maximo) maximo = a[i];
int posicion = 0; // B: candidato inicial en a[0].
for (int i = 1; i < 3; i++)
if (a[i] > a[posicion]) posicion = i;
cout << maximo << " " << a[posicion] << "\n";El máximo debe venir del arreglo
Ningún elemento supera cero, así que la primera versión termina con un valor que ni siquiera apareció. La segunda empieza con −8, lo cambia por −3 y lo conserva al ver −5. Después de cada paso, su candidato es el máximo de los elementos ya recorridos. Esta inicialización requiere un arreglo no vacío; si puede estar vacío, el enunciado debe definir qué respuesta corresponde.
← 02 - La competencia y la estrategia · Ruta de Aprendizaje · 04 - Matrices →