Busqueda

Operación de búsqueda lineal: idea y propósito

Buscar 30

[🟦, ⬜, ⬜, ⬜]   (10 == 30) → no
  0   1   2   3

Paso 1 (i = 0)

Comparamos items[0] con 30:

Buscar 30

[⬜, 🟦, ⬜, ⬜]   (20 == 30) → no
  0   1   2   3

Paso 2 (i = 1)

Comparamos items[1] con 30:

Buscar 30

[⬜, ⬜, 🟩, ⬜]   (30 == 30) → ¡sí!
  0   1   2   3

Paso 3 (i = 2)

Comparamos items[2] con 30:

Resultado: devolvemos 2 y termina la búsqueda.

Buscar 100 (caso no encontrado)

i = 0 → 1 → 2 → 3 No hay coincidencias en ninguna posición válida.

[🟦, ⬜, ⬜, ⬜]   (10 == 100) → no
[⬜, 🟦, ⬜, ⬜]   (20 == 100) → no
[⬜, ⬜, 🟦, ⬜]   (30 == 100) → no
[⬜, ⬜, ⬜, 🟦]   (50 == 100) → no

Como no retornamos dentro del bucle, al final devolvemos -1.

Código (esqueleto)

public int buscarEn(int item) {
    // 1) Recorrer desde i = 0 hasta i < contador
    // 2) Comparar items[i] con item
    // 3) Si coincide, devolver i
    // 4) Si termina el bucle sin coincidencias, devolver -1
}

Código paso a paso (implementación)

public int buscarEn(int item) {
    for (int i = 0; i < contador; i++) {
        
    }
    return -1; // no se encontró en ninguna posición válida
}

Código paso a paso (implementación)

public int buscarEn(int item) {
    for (int i = 0; i < contador; i++) {
        if (items[i] == item) {
           
        }
    }
    return -1; // no se encontró en ninguna posición válida
}

Código paso a paso (implementación)

public int buscarEn(int item) {
    for (int i = 0; i < contador; i++) {
        if (items[i] == item) {
            return i; // encontrado → devolvemos el índice y salimos
        }
    }
    return -1; // no se encontró en ninguna posición válida
}

Código final (compacto y claro)

public int buscarEn(int item) {
    for (int i = 0; i < contador; i++)
        if (items[i] == item)
            return i;
    return -1;
}

Prueba rápida en Main

public class Main {
    public static void main(String[] args) {
        Arreglo numeros = new Arreglo(3);
        numeros.insertar(10);
        numeros.insertar(20);
        numeros.insertar(30);
        numeros.insertar(50);

        System.out.println(numeros.buscarEn(30));  // → 2
        System.out.println(numeros.buscarEn(100)); // → -1
    }
}

Salida esperada:

2
-1

Complejidad temporal (Big-O): intuición visual

Pensamos en cuántas comparaciones hace buscarEn(item) antes de decidir.

Complejidad temporal (Big-O): intuición visual

[10, 20, 30, 50]   n = 4

Caso mejor (i=0):  ✓ — 1 comparación → O(1)
Caso típico (i=2): ✗, ✗, ✓ — 3 comparaciones
Caso peor (i=3):   ✗, ✗, ✗, ✓ — 4 comparaciones → O(n)
No está (100):     ✗, ✗, ✗, ✗ — 4 comparaciones → O(n)

Complejidad temporal (Big-O): intuición visual

La salida temprana ayuda cuando aparece pronto, pero si está al final (o no está), se recorre todo.

Contemos bien: función de costo T(n)

Para un arreglo de tamaño n y un item:

• Si item está en la posición j (0-indexado), T(n) = j + 1 (comparaciones).

• Si item no está, T(n) = n (comparamos todo y devolvemos -1).

Contemos bien: función de costo T(n)

Por tanto:

1 ≤ T(n) ≤ n   ⇒   T(n) = O(n)

Mejor, peor y promedio (sin esconder nada)

• Mejor caso: item en la primera celda → 1 comparación → O(1).

Mejor, peor y promedio (sin esconder nada)

• Peor caso: item al final o no está → n comparaciones → O(n).

Mejor, peor y promedio (sin esconder nada)

• Promedio (sin repeticiones, posición equiprobable): si el item está, E[T] = (n + 1) / 2. si puede no estar con prob. p: E[T] = (1 − p)·(n + 1)/2 + p·n = O(n).

Mejor, peor y promedio (sin esconder nada)

La salida temprana mejora la constante esperada, no el orden de crecimiento.

¿Qué significa en la práctica?

• Con n = 1,000,000 y el item al final o ausente: haces ~1 millón de comparaciones.

• Con n = 1,000,000 y el item uniforme al azar (presente): esperas ~500 mil comparaciones.

Conclusión operativa: sigue siendo lineal; crece proporcional a n.

Resumen final (para tu slide)

• Mejor caso: O(1) (aparece de primeras).
• Peor caso: O(n) (al final o no está).
• Promedio: O(n).
• Conclusión Big-O (peor caso): O(n).