Búsqueda binaria clásica sin errores
Domine el bucle de low, high y mid
Búsqueda binaria clásica sin errores es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Reduzca a la mitad el espacio de búsqueda
La búsqueda binaria encuentra un valor en una lista ordenada reduciendo a la mitad el rango en cada paso. Así, un recorrido lento O(n) se convierte en una búsqueda rápida O(log n).
a = [1, 3, 5, 7, 9] # must be sortedLos datos deben estar ordenados
La búsqueda binaria solo funciona con datos ordenados. Si la lista no está ordenada, ordénela primero; de lo contrario, el resultado carecerá de sentido y será incorrecto.
a.sort() # ascending order requiredDos límites
Comience con dos punteros: low en el índice 0 y high en el último índice. Si el objetivo está presente, siempre se encontrará entre ellos.
low, high = 0, len(a) - 1Encuentre el punto medio de forma segura
Calcule mid como low + (high - low) // 2. En Python el desbordamiento no es un problema, pero esta forma es el hábito seguro en cualquier lugar.
mid = low + (high - low) // 2Tres resultados
Compare a[mid] con el objetivo. Puede que lo haya encontrado, que sea demasiado pequeño o que sea demasiado grande. Cada caso reduce el rango de una forma distinta.
if a[mid] == target:
return midDemasiado pequeño: vaya a la derecha
Si a[mid] es menor que el objetivo, la respuesta debe estar a la derecha. Mueva low a mid + 1 y descarte la mitad izquierda.
elif a[mid] < target:
low = mid + 1Demasiado grande: vaya a la izquierda
Si a[mid] es mayor que el objetivo, busque en la mitad izquierda. Mueva high a mid - 1 para no volver a comprobar mid.
else:
high = mid - 1La condición del bucle
Continúe mientras low sea menor o igual que high. Cuando se crucen, el rango estará vacío y el objetivo no estará presente.
while low <= high:
mid = low + (high - low) // 2Indique que no se encontró
Si el bucle termina sin encontrar coincidencias, el valor no está presente. Devuelva -1 por convenio para que quien llame pueda distinguir el éxito del fallo.
return -1 # target not in listLa trampa del desfase de uno
El error clásico consiste en olvidar el +1 o -1 al mover un puntero. Si lo omite, mid se vuelve a comprobar indefinidamente y se produce un bucle infinito.
low = mid + 1 # not low = midUse la biblioteca cuando pueda
Para una simple comprobación de pertenencia, el módulo bisect de Python ya ofrece una búsqueda sin errores. Escriba el bucle manualmente solo cuando necesite una lógica personalizada.
import bisect
i = bisect.bisect_left(a, target)Comprobación rápida
Reflexione sobre qué mantiene el bucle bajo control.
Repaso: busque sin errores
Ya puede establecer low y high, calcular mid de forma segura, reducir el lado correcto y evitar la trampa del desfase de uno. La búsqueda logarítmica está a su alcance. 🎯
Preguntas frecuentes
¿La lección «Búsqueda binaria clásica sin errores» es gratis?
Sí — el texto completo de «Búsqueda binaria clásica sin errores» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Búsqueda binaria clásica sin errores»?
Domine el bucle de low, high y mid Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Búsqueda binaria clásica sin errores»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Búsqueda binaria clásica sin errores
- bisect_left y bisect_right
- First True: búsqueda binaria por predicado
- Búsqueda binaria sobre la respuesta