3.05 · Búsqueda: Secuencial vs Binaria

🧠 Teoría y conceptos — 🐢 1. Búsqueda Lineal (Secuencial)

Figura: Búsqueda lineal - recorrido completo

Idea: revisar cada elemento del arreglo, de izquierda a derecha, hasta encontrar el objetivo o llegar al final.

int buscarLineal(int arr[], int n, int objetivo) {

for (int i = 0; i < n; i++) {
if (arr[i] == objetivo) {
return i;  // encontrado, devuelvo la posición

}

}

return -1;  // no encontrado

}

Uso:

int datos[] = {7, 2, 9, 1, 5, 8};

int n = 6;

int pos = buscarLineal(datos, n, 5);

if (pos != -1) {
cout << "Encontrado en posición " << pos << endl;  // 4
} else {
cout << "No existe" << endl;

}

Análisis

• Mejor caso: el elemento está al inicio → 1 paso (O(1)).
• Peor caso: el elemento está al final o no existe → n pasos (O(n)).
• Caso promedio: n/2 pasos (también O(n)).

¿Cuándo usarla?

• El arreglo es pequeño (decenas de elementos).
• El arreglo no está ordenado y ordenarlo costaría más que buscar linealmente.
• Solo vas a buscar una vez.

🐇 2. Búsqueda Binaria

Idea: si el arreglo está ordenado, puedes descartar la mitad del espacio de búsqueda con cada comparación.

La estrategia, explicada con el ejemplo de tu cuaderno

Busca el 5 en [1, 2, 3, 4, 5, 6, 7, 8, 9]:

Paso 1:

• Rango: [0..8], medio = (0+8)/2 = 4, valor = 5. ¡Encontrado!
• Pasos: 1.

Pero en general no tendrás tanta suerte. Busca el 8 en [1, 3, 5, 7, 9, 11, 13, 15, 17]:

Figura: Búsqueda binaria - paso 1

Paso 1:

• Rango: [0..8], medio = 4, valor = 9.
• 8 < 9 → descartar mitad derecha.

Figura: Búsqueda binaria - paso 2

Paso 2:

• Rango: [0..3], medio = 1 (o 2, depende del cálculo), valor = 3.
• 8 > 3 → descartar mitad izquierda.

Figura: Búsqueda binaria - paso 3

Paso 3:

• Rango: [2..3], medio = 2, valor = 5.
• 8 > 5 → descartar mitad izquierda.
• Rango: [3..3], medio = 3, valor = 7.
• 8 > 7 → rango vacío. No encontrado.

Total: 4 pasos vs 9 de la búsqueda lineal. No parece mucho, pero escala brutalmente.

Implementación

int buscarBinaria(int arr[], int n, int objetivo) {

int izq = 0;

int der = n - 1;

while (izq <= der) {

int medio = izq + (der - izq) / 2; // evita overflow

if (arr[medio] == objetivo) {
return medio;  // encontrado
} else if (arr[medio] < objetivo) {

izq = medio + 1; // descartar izquierda

} else {

der = medio - 1; // descartar derecha

}

}

return -1;  // no encontrado

}

Análisis

• Cada paso descarta la mitad del rango.
• Con n elementos, el número de pasos es ⌊log₂(n)⌋ + 1.

Para n = mil millones, la búsqueda binaria hace 30 pasos. La lineal, mil millones. Con datos grandes, la diferencia es la utilidad del programa.

🧪 4. Medición empírica: verlo con tus ojos

#include <iostream>
#include <chrono>
#include <algorithm>
using namespace std;

// ... funciones buscarLineal y buscarBinaria ...

int main() {

const int N = 1000000;

int* datos = new int[N];
for (int i = 0; i < N; i++) datos[i] = i;  // 0, 1, 2, ..., 999999

int objetivo = 999999; // peor caso: al final

// Lineal

auto t1 = chrono::high_resolution_clock::now();

int pos1 = buscarLineal(datos, N, objetivo);

auto t2 = chrono::high_resolution_clock::now();

auto tiempoLineal = chrono::duration_cast<chrono::microseconds>(t2 - t1);

// Binaria

auto t3 = chrono::high_resolution_clock::now();

int pos2 = buscarBinaria(datos, N, objetivo);

auto t4 = chrono::high_resolution_clock::now();

auto tiempoBinaria = chrono::duration_cast<chrono::microseconds>(t4 - t3);

cout << "Lineal:  " << tiempoLineal.count() << " us (pos=" << pos1 << ")" << endl;
cout << "Binaria: " << tiempoBinaria.count() << " us (pos=" << pos2 << ")" << endl;
cout << "Binaria fue " << (double)tiempoLineal.count() / max(1L, (long)tiempoBinaria.count())

<< "x más rápida" << endl;

delete[] datos;

return 0;

}

Salida típica (depende del hardware):

Lineal: 3200 us

Binaria: 1 us

Binaria fue 3200x más rápida

🐍 5. Búsqueda binaria en Python (bonus)

Python tiene bisect que ya implementa esto:

import bisect

arr = [1, 3, 5, 7, 9]

pos = bisect.bisect_left(arr, 5) # 2

Y en C++ STL también:

#include <algorithm>
int arr[] = {1, 3, 5, 7, 9};

int n = 5;

int* pos = lower_bound(arr, arr + n, 5);

if (pos != arr + n && *pos == 5) {
cout << "Encontrado en posición " << (pos - arr) << endl;

}

Regla profesional: no reimplementes algoritmos clásicos en producción. Usa la librería estándar. Pero primero entiéndelo.

🧪 8. LAB 3.5 — Benchmark de Búsquedas (4 h)

Descripción

Crea un programa que compare las dos búsquedas con diferentes tamaños de arreglo:

1. Genera arreglos de tamaño 10, 100, 1 000, 10 000, 100 000, 1 000 000.
2. Para cada tamaño:

• Llena el arreglo con valores aleatorios.
• Mide el tiempo de búsqueda lineal buscando un valor al final.
• Ordena el arreglo con sort().
• Mide el tiempo de búsqueda binaria buscando el mismo valor.

1. Imprime una tabla con: tamaño, tiempo lineal, tiempo binaria, ratio.
2. Búsqueda interactiva: pide al usuario un valor y usa búsqueda binaria (sobre un arreglo ordenado) para encontrarlo.

Rúbrica de evaluación

Bonus XP

• +30 XP si generas una gráfica ASCII del crecimiento (eje Y: tiempo, eje X: tamaño).
• +20 XP si agregas búsqueda de primera ocurrencia (si hay duplicados, encuentra el de menor índice).
• +20 XP si mides también el costo de ordenar y lo incluyes en el análisis (¿cuándo se justifica?).

🔚 10. Cierre — Cuaderno del programador

1. Trazar el árbol de búsqueda binaria con un ejemplo de n=7 en tu cuaderno. Marca qué mitad se descarta en cada paso.
2. Calcular: si tuvieras un arreglo de 1 billón de elementos, ¿cuántos pasos haría la búsqueda binaria? (log₂(10¹²) ≈ 40).
3. Reflexión: en tu carrera profesional, ¿en qué sistema usarías búsqueda binaria? (Catálogo de productos, base de datos, etc.) ¿Y en cuál sería mejor la lineal?
4. Compromiso: antes de cada búsqueda, pregunta primero si el arreglo está ordenado. Te ahorrará horas de bugs.

🏅 Insignia y XP del tema

🔗 ¿Qué sigue?

Tema 3.6 — Ordenamiento: Burbuja, Selección, Inserción. Si la búsqueda binaria requiere datos ordenados, ¿cómo los ordenamos? Hay tres algoritmos básicos que debes dominar antes de pasar a QuickSort o MergeSort. Cada uno tiene una "personalidad" diferente — y verás cuál es el más natural para tu cerebro.

Antes de avanzar:

• [ ] LAB 3.5 entregado y funcionando
• [ ] Quest mixto respondido en el cuaderno
• [ ] Reflexión escrita

*"Buscar es fácil. Buscar rápido es ingeniería."*

⚠️ Errores típicos — ⚠️ 7. Errores típicos del razonamiento

Error 1: Usar búsqueda binaria en un arreglo desordenado

int arr[] = {5, 2, 8, 1, 9};  // NO está ordenado

int pos = buscarBinaria(arr, 5, 8); // FALSO resultado

La búsqueda binaria asume que arr[0] ≤ arr[1] ≤ .... Si no es así, el resultado es basura. Verifica que esté ordenado antes.

Error 2: Bucle infinito por mal cálculo del medio

int medio = (izq + der) / 2; // puede overflow con números grandes

Usa:

int medio = izq + (der - izq) / 2;

Es matemáticamente equivalente pero evita el overflow.

Error 3: No actualizar bien los extremos

if (arr[medio] < objetivo) {

izq = medio; // MAL: puede entrar en bucle infinito

}

// BIEN:

izq = medio + 1;

Regla: cuando descartas, incluye el medio en el descarte. Es el que ya comparaste y no es el objetivo.

Error 4: Confundir "no encontrado" con "está al final"

int pos = buscarBinaria(arr, n, x);

cout << arr[pos];  // CRASH si pos == -1

Siempre chequea el retorno antes de usarlo.

Error 5: Olvidar devolver la posición

if (arr[medio] == objetivo) {
cout << "Encontrado";  // No devuelve nada, la función retorna basura

}

return -1;  // esto se ejecuta igual
Si tu función promete devolver la posición, devuélvela. El return debe estar dentro del if.

🤖 IA como copiloto — 🤖 6. AI Mission — "Dime la condición de paro"

Objetivo: entender la condición de paro de la búsqueda binaria, que es donde se confunde el 80% de los estudiantes.

Prompt sugerido:

"Tengo este código de búsqueda binaria en C++. Explícame con una analogía por qué la condición del `while` es `izq <= der` y no `izq < der`. Y por qué cuando descartamos la mitad izquierda hacemos `izq = medio + 1` y no `izq = medio`."

Lo que NO debes hacer:

• Pedirle la implementación de un LAB.
• Aceptar la analogía sin verificarla trazando un ejemplo.

Lo que SÍ debes hacer:

• Dibujar en tu cuaderno el árbol de decisiones de la búsqueda binaria con un ejemplo.
• Reescribir la analogía con tus palabras.

Ritual de 3 min: si la analogía no te queda clara, traza un caso de n=5 en papel antes de volver a preguntar.

📝 Quest · Cuestionario — 📝 Quest — Reactivos para autoevaluación

Sección A · Opción múltiple

Elige la opción correcta (A, B, C o D). Las respuestas están en la sección Respuestas modelo.

1. ¿Cuál es la complejidad de la búsqueda secuencial?
   • O(1)
   • O(n)
   • O(log n)
   • O(n²)
2. ¿Cuál es la complejidad de la búsqueda binaria?
   • O(1)
   • O(log n)
   • O(n)
   • O(n log n)
3. ¿Qué requisito tiene la búsqueda binaria?
   • Arreglo de cualquier tamaño
   • Arreglo ORDENADO
   • Solo números pares
   • Solo strings
4. Si buscas 50 en [10, 20, 30, 40, 50, 60, 70] usando binaria, ¿cuántos pasos?
   • 1
   • 2
   • 3
   • 7
5. ¿Cómo se calcula el punto medio en binaria?
   • (low + high) / 2
   • low + high
   • high - low
   • low * 2
6. Búsqueda binaria vs secuencial: ¿cuándo es mejor la binaria?
   • Siempre
   • En datos ordenados grandes donde importa la velocidad
   • En datos desordenados
   • Solo con strings
7. ¿Qué pasa si los datos están desordenados y usas binaria?
   • Funciona igual
   • Resultado incorrecto
   • Es más rápido
   • Error de compilación
8. ¿Cuál es la diferencia entre búsqueda y ordenamiento?
   • Son iguales
   • Búsqueda encuentra, ordenamiento pone en orden
   • Ordenamiento busca
   • Búsqueda ordena
9. ¿Cuántas comparaciones hace la búsqueda binaria en el peor caso con n=1024?
   • 10
   • 11
   • 1024
   • 100
10. ¿Búsqueda binaria requiere acceso aleatorio?
    • No
    • Sí, para acceder al elemento medio en O(1)
    • Solo en arrays
    • Solo en listas

Sección B · Preguntas abiertas

Desarrolla tu respuesta en al menos 3 líneas. Compara con la respuesta modelo después de escribir.

1. ¿Por qué la búsqueda binaria solo funciona en datos ordenados? Da un ejemplo donde falla.
   → Escribe tu respuesta aquí (en tu cuaderno o mentalmente)…
2. Diseña un algoritmo que combine búsqueda binaria con la condición de "primera ocurrencia" de un elemento repetido.
   → Escribe tu respuesta aquí (en tu cuaderno o mentalmente)…
3. ¿Cuándo es mejor búsqueda lineal sobre binaria? Da 2 casos.
   → Escribe tu respuesta aquí (en tu cuaderno o mentalmente)…