Un vector ordenado de 4096 elementos. ¿Cuántas
veces parte el rango por la mitad lower_bound hasta quedarse
con una sola posición?
2. Borrar k elementos uno a uno
Un vector de n elementos y k de ellos, repartidos
en el medio, se borran con it = v.erase(it). ¿Qué costo tiene
en tiempo?
3. Un millón de consultas
Un vector de un millón de números y un millón de
preguntas "¿está x?". ¿Cuál cuesta menos comparaciones?
4. El espacio de sort
Aparte del vector que ordena, ¿cuánto espacio
pide sort?
Lo que quedó
Partir por la mitad cuesta log n y exige orden;
correr lo que sigue cuesta n por borrado; y una decisión de diseño,
ordenar una vez o recibir por valor, es la que fija el costo de todo lo
demás.