Contexto
En ingeniería de software no alcanza con que un algoritmo “parezca andar bien” en un par de ejemplos. Hace falta demostrar que produce el resultado correcto bajo cualquier condición y entender cómo escala su consumo de tiempo y memoria a medida que el volumen de datos crece.
Un contrato riguroso (entradas, precondiciones, postcondiciones y tratamiento de errores) y la notación Big O son los cimientos que diferencian un parche improvisado de una solución técnica sólida.
Consigna
Vas a implementar dos clases:
BusquedaSegura.java: implementa los algoritmos de búsqueda lineal y binaria junto con su análisis teórico.MainVerificacion.java: suite de pruebas que comprueba el cumplimiento del contrato en casos felices, límites y erróneos.
1. Especificación del contrato formal
Para cada algoritmo debés dejar documentado en su cabecera:
- Entradas: qué parámetros recibe.
- Precondición: qué condiciones deben cumplirse antes de invocarlo (por ejemplo, en búsqueda binaria: el array debe estar ordenado ascendentemente y no ser
null). - Postcondición: qué garantiza el método al terminar (el índice retornado contiene el valor buscado).
- Error / Casos especiales: qué ocurre si la entrada es
null, está vacía o el elemento no existe (retornar el valor centinela-1).
2. Búsqueda binaria e invariante de bucle
En busquedaBinaria(int[] ordenados, int objetivo):
- Calculá el índice medio con
medio = inicio + (fin - inicio) / 2. - El invariante de bucle establece que: si
objetivoestá presente en el array, entonces necesariamente se encuentra dentro del subrango actual[inicio, fin]. - En cada paso, al comparar
ordenados[medio]conobjetivo, descartá de forma segura la mitad del espacio sin romper el invariante.
3. Comparativa asintótica y código limpio
Implementá compararComplejidad(int n) para ilustrar de forma numérica por qué un algoritmo $O(\log n)$ es exponencialmente superior a uno $O(n)$ en conjuntos de datos grandes, demostrando que optimizar el orden asintótico rinde órdenes de magnitud más que cualquier microoptimización sintáctica.