Posición para insertar
`ordenada` viene de menor a mayor. Devolvé el índice donde habría que insertar `x` para que la lista SIGA ordenada (la primera posición cuyo valor sea ≥ x). Ejemplo: posicion_para_insertar([1, 3, 5], 4) → 2
Entrá y llevá tu progreso —ejercicios, medallas y Pokémon— a cualquier dispositivo. 🔄
Si tu cuenta ya tiene progreso guardado, se carga ese al entrar.
Entraste como . Tu progreso se sincroniza solo. 🔄
`ordenada` viene de menor a mayor. Devolvé el índice donde habría que insertar `x` para que la lista SIGA ordenada (la primera posición cuyo valor sea ≥ x). Ejemplo: posicion_para_insertar([1, 3, 5], 4) → 2
🎯 Meta: buscar datos de dos formas y entender por qué una es muchísimo más rápida.
Buscar es la operación más común de todas. Hay dos formas clásicas, y la diferencia entre ellas es enorme cuando los datos crecen.
Mirás uno por uno hasta encontrarlo. Simple y funciona en cualquier lista (ordenada o no):
def busqueda_lineal(lista, x):
for i, v in enumerate(lista):
if v == x:
return i
return -1 # no está
Si la lista tiene un millón de elementos, en el peor caso hacés un millón de comparaciones. Eso es O(n): el tiempo crece igual que el tamaño.
Si la lista está ordenada, podés ser mucho más vivo: mirás el del medio y descartás la mitad que no sirve. Repetís hasta encontrarlo:
def busqueda_binaria(ordenada, x):
lo, hi = 0, len(ordenada) - 1
while lo <= hi:
mid = (lo + hi) // 2
if ordenada[mid] == x:
return mid
if ordenada[mid] < x:
lo = mid + 1 # descartá la mitad izquierda
else:
hi = mid - 1 # descartá la mitad derecha
return -1
Cada paso parte el problema al medio: un millón de elementos se resuelve en ~20 pasos. Eso es O(log n) — abismalmente más rápido.
⚠️ La binaria SOLO funciona si la lista está ordenada. Por eso el próximo capítulo es ordenar.
P: La búsqueda binaria requiere que la lista esté…
+ ordenada
- vacía
- sin repetidos
> Parte el rango al medio descartando mitades; por eso necesita orden.
P: Buscar en un millón de elementos: lineal vs binaria…
+ binaria ~20 pasos; lineal hasta un millón
- las dos tardan igual
- la lineal es más rápida
> O(log n) (binaria) es muchísimo mejor que O(n) (lineal).
🔎 La Líder Katy te espera para construir buscadores.