Precondición: arreglo no nulo y ordenado
Un algoritmo empieza con un contrato verificable: entradas, precondición y postcondición. La precondición exige que ordenados no sea null y esté en orden ascendente.
Un algoritmo empieza con un contrato verificable: entradas, precondición y postcondición.
La precondición exige que ordenados no sea null y esté en orden ascendente.
Un algoritmo empieza con un contrato verificable: entradas, precondición y postcondición. La precondición exige que ordenados no sea null y esté en orden ascendente.
La postcondición promete devolver el índice de objetivo = 23, o -1 si no está.
Si la entrada es inválida o el valor falta, -1 actúa como valor centinela documentado.
La postcondición promete devolver el índice de objetivo = 23, o -1 si no está. Si la entrada es inválida o el valor falta, -1 actúa como valor centinela documentado.
La búsqueda lineal recorre el arreglo desde el inicio, comparando casillero por casillero.
Para hallar 23 en el índice 5, revisa seis posiciones: en el peor caso crece como O(n).
Es un algoritmo correcto, pero ignora que los datos ya estaban ordenados.
La búsqueda lineal recorre el arreglo desde el inicio, comparando casillero por casillero. Para hallar 23 en el índice 5, revisa seis posiciones: en el peor caso crece como O(n). Es un algoritmo correcto, pero ignora que los datos ya estaban ordenados.
La búsqueda binaria aprovecha el orden manteniendo un rango [izquierda..derecha].
Su invariante de bucle afirma: si objetivo existe, vive dentro de [izquierda..derecha].
La búsqueda binaria aprovecha el orden manteniendo un rango [izquierda..derecha]. Su invariante de bucle afirma: si objetivo existe, vive dentro de [izquierda..derecha].
En la primera vuelta, calcula medio = izquierda + (derecha - izquierda) / 2, que da 3.
Lee ordenados[3] = 12 y lo compara con 23: como 12 < 23, el objetivo está a la derecha.
En la primera vuelta, calcula medio = izquierda + (derecha - izquierda) / 2, que da 3. Lee ordenados[3] = 12 y lo compara con 23: como 12 < 23, el objetivo está a la derecha.
Una sola comparación descarta la mitad izquierda completa: los índices 0 a 3.
Actualiza izquierda = medio + 1 (4): el invariante de bucle se conserva en [4..6].
Una sola comparación descarta la mitad izquierda completa: los índices 0 a 3. Actualiza izquierda = medio + 1 (4): el invariante de bucle se conserva en [4..6].
En la segunda vuelta, el nuevo medio entre 4 y 6 es el índice 5.
Allí encuentra ordenados[5] = 23 y devuelve el índice 5, cumpliendo la postcondición.
Al partir el espacio a la mitad en cada paso, el costo baja de O(n) a O(log n).
En la segunda vuelta, el nuevo medio entre 4 y 6 es el índice 5. Allí encuentra ordenados[5] = 23 y devuelve el índice 5, cumpliendo la postcondición. Al partir el espacio a la mitad en cada paso, el costo baja de O(n) a O(log n).
Un buen diseño une tres piezas: contrato claro, corrección por invariante y complejidad.
Con un millón de datos, O(n) puede hacer un millón de pasos; O(log n), apenas veinte.
Un buen diseño une tres piezas: contrato claro, corrección por invariante y complejidad. Con un millón de datos, O(n) puede hacer un millón de pasos; O(log n), apenas veinte.