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:

  1. BusquedaSegura.java: implementa los algoritmos de búsqueda lineal y binaria junto con su análisis teórico.
  2. 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 objetivo está presente en el array, entonces necesariamente se encuentra dentro del subrango actual [inicio, fin].
  • En cada paso, al comparar ordenados[medio] con objetivo, 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.