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: n

Con entrada 5 seguida de 7 3 9 2 5, se guardan cinco números y se imprime 5. El dibujo muestra esas cinco casillas.

70319223545a[5]fuera de rangoa.front()a.back()a.size() es 5, pero la última posición es 4

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:

ia[i]a[mejor] hasta ahora¿a[i] > a[mejor]?mejor después
193sí1
229no1
379no1

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.

Buscamos x = 2, de izquierda a derecha39272i = 03 ≠ 2: seguir39272i = 19 ≠ 2: seguir3091227324i = 22 = 2: pararBorde grueso: la comparación de esa vuelta.Respuesta: posición 2. No seguimos al otro 2.

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 iValor a[i]¿Es 2?Qué ocurre
03nopos sigue en −1; avanzamos
19nopos sigue en −1; avanzamos
22síguardamos pos = 2 y salimos del ciclo
3 y 4no 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:

PreguntaRespuestaQué debemos conservar y cuándo terminar
¿Está?síbasta el primer acierto
¿Dónde aparece por primera vez?posición 2guardar el índice y cortar
¿Dónde aparece por última vez?posición 4reemplazar el índice en cada acierto y seguir
¿Cuántas veces aparece?2 vecesincrementar 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 guardadosMemoria de los elementos
Un millón de int4 MB
Un millón de long long8 MB
Mil millones de int4 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.

Ejemplo: size() = 5, capacity() = 800010203045675 elementos: 20 bytesBloque para 8: 32 bytes, si sizeof(int) = 4Las casillas punteadas aún no son elementos.reserve(8) garantiza capacidad ≥ 8; no tamaño 8.Falta sumar el costo del vector y del programa.

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.

🏋️ 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.

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.

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):

#ProblemaFaseQué practica
1Rey De Los PiratasRegional 2023el mejor con desempate, en una pasada
2LlavesRegional 2020recorrer con condición y contador
3Tormenta ChinaRegional 2021el segundo menor distinto (n ≤ 10⁶)
4Secuencia de ADNRegional 2019ventanas de tamaño 3
5⭐ Carta de navegaciónNacional 2025doble pasada sobre un arreglo circular

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1In Search of an Easy Problem (1030A)★ (800)¿hay algún 1? — búsqueda con corte
2Stones on the Table (266A)★ (800)comparar vecinos
3Vasya the Hipster (581A)★ (800)mínimos y aritmética
4Kefa 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";

← 02 - La competencia y la estrategia · Ruta de Aprendizaje · 04 - Matrices →