Búsqueda binaria clásica: izquierda, derecha y centro
Implemente la búsqueda binaria de forma iterativa y recursiva, domine los detalles de los desfases de uno en los límites lo/hi y compruebe la corrección con entradas límite.
Búsqueda binaria clásica: izquierda, derecha y centro es una lección gratuita de Coding Interview Prep 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 Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Por qué es importante la búsqueda binaria
La búsqueda binaria reduce un recorrido lineal de O(n) a O(log n) al dividir por la mitad el espacio de búsqueda en cada paso. En un arreglo de un millón de elementos, un recorrido lineal necesita hasta 1.000.000 de comparaciones, mientras que la búsqueda binaria necesita como máximo 20. Esta eficiencia la convierte en uno de los algoritmos más evaluados en las entrevistas de programación.
La idea fundamental es que un arreglo ordenado permite decidir, después de una sola comparación, qué mitad de los datos restantes se puede descartar por completo.
El esquema de izquierda, medio y derecha
La búsqueda binaria utiliza tres índices límite: lo (límite izquierdo), hi (límite derecho) y mid (punto medio). En cada iteración, calcule mid = (lo + hi) // 2 y compare el objetivo con arr[mid]. Si el objetivo es menor, mueva hi = mid - 1; si es mayor, mueva lo = mid + 1; si es igual, lo habrá encontrado.
El bucle continúa mientras lo <= hi. Cuando el bucle termina sin encontrar el objetivo, devuelva -1.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6)) # -1Cómo evitar el desbordamiento de enteros en mid
La expresión mid = (lo + hi) // 2 puede provocar un desbordamiento de enteros en lenguajes con enteros de ancho fijo (Java, C++). Los enteros de Python tienen precisión arbitraria, por lo que nunca se produce un desbordamiento, pero en una entrevista se espera que conozca la alternativa segura: mid = lo + (hi - lo) // 2.
Esta forma calcula el mismo punto medio, pero suma únicamente la mitad de la distancia a lo en lugar de sumar primero ambos punteros. Mencionarlo en una entrevista demuestra que conoce los aspectos de bajo nivel.
# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2 # fine in Python
mid_safe = lo + (hi - lo) // 2 # same result, no overflow risk
print(mid_unsafe == mid_safe) # TrueLímites inclusivos frente a exclusivos
Una de las partes más complicadas de la búsqueda binaria es decidir si hi apunta al último índice válido (inclusivo, hi = len(arr) - 1) o a una posición después del final (exclusivo, hi = len(arr)). Las distintas convenciones requieren condiciones de bucle y actualizaciones de límites diferentes.
Con límites inclusivos, utilice while lo <= hi y actualice hi = mid - 1. Con límites exclusivos, utilice while lo < hi y actualice hi = mid. Mezclar las convenciones es la causa más común de errores en las implementaciones de búsqueda binaria.
# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
lo, hi = 0, len(arr) # hi is one past last
while lo < hi: # strictly less than
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # NOT mid - 1
return lo if lo < len(arr) and arr[lo] == target else -1
print(search_exclusive([2, 4, 6, 8, 10], 6)) # 2Búsqueda binaria recursiva
La búsqueda binaria se puede escribir de forma recursiva pasando los límites actualizados lo y hi a través de la pila de llamadas. Cada llamada recursiva reduce el espacio de búsqueda a la mitad, por lo que la profundidad es O(log n). El caso base se da cuando lo > hi (no se encontró el elemento) o cuando arr[mid] == target (se encontró).
La versión iterativa se prefiere en el código de producción porque evita el coste adicional de los marcos de pila, pero la versión recursiva comunica con mayor claridad la estructura de divide y vencerás en una pizarra.
def binary_search_rec(arr, target, lo, hi):
if lo > hi:
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_rec(arr, target, mid + 1, hi)
else:
return binary_search_rec(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1)) # 4Casos límite: arreglo vacío y elemento único
Una búsqueda binaria robusta debe gestionar los casos límite sin bloquearse. Los tres más comunes son: un arreglo vacío (el bucle nunca se ejecuta y se devuelve correctamente -1), un arreglo de un solo elemento (mid, lo y hi tienen el mismo valor, por lo que basta una comparación) y objetivos fuera del rango (lo acaba superando a hi y se devuelve -1).
Verifique siempre su implementación con estas entradas antes de pasar a las preguntas adicionales de una entrevista.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([], 5)) # -1 (empty)
print(binary_search([7], 7)) # 0 (single, found)
print(binary_search([7], 3)) # -1 (single, not found)
print(binary_search([1,3,5], 0)) # -1 (below range)
print(binary_search([1,3,5], 9)) # -1 (above range)Complejidad temporal y espacial
La búsqueda binaria tiene una complejidad temporal de O(log n) porque cada comparación divide a la mitad el espacio de búsqueda. Después de k comparaciones, el espacio restante es n/2^k; la búsqueda termina cuando este valor llega a 1, por lo que k = log₂ n.
La complejidad espacial es O(1) para la versión iterativa (solo tres variables enteras) y O(log n) para la versión recursiva debido a la profundidad de la pila de llamadas. En una entrevista, indique siempre ambas y prefiera la forma iterativa cuando la memoria sea limitada.
import math
for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
steps = math.ceil(math.log2(n + 1))
print(f'n={n:>12,} max comparisons={steps}')Búsqueda de coincidencia exacta frente a búsqueda de límites
La búsqueda binaria clásica devuelve cualquier índice donde exista el objetivo. Sin embargo, muchos problemas de entrevistas solicitan la primera o la última aparición de un objetivo. En esos casos debe continuar buscando incluso después de encontrar una coincidencia: en lugar de devolver el resultado inmediatamente, ajuste el límite y siga buscando.
Al buscar la primera aparición, después de encontrar arr[mid] == target, guarde mid como candidato y establezca hi = mid - 1. Para buscar la última aparición, establezca lo = mid + 1.
def first_occurrence(arr, target):
lo, hi, result = 0, len(arr) - 1, -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
result = mid
hi = mid - 1 # keep searching left
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return result
print(first_occurrence([1, 2, 2, 2, 3], 2)) # 1Uso del módulo bisect de Python
La biblioteca estándar de Python proporciona bisect.bisect_left(arr, x) y bisect.bisect_right(arr, x) para realizar búsquedas binarias listas para producción. bisect_left devuelve el índice más a la izquierda donde se puede insertar x para mantener el arreglo ordenado; en la práctica, encuentra la primera posición donde arr[i] >= x.
Es posible que los entrevistadores le permitan utilizar bisect; confírmelo siempre primero. Aun así, es fundamental saber cómo funciona internamente (es una búsqueda binaria de O(log n)).
import bisect
arr = [1, 2, 2, 2, 3, 5]
print(bisect.bisect_left(arr, 2)) # 1 (first 2)
print(bisect.bisect_right(arr, 2)) # 4 (after last 2)
# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target) # TrueErrores comunes en la búsqueda binaria
Tres errores causan la mayoría de los fallos de búsqueda binaria en las entrevistas. Primero, una condición de bucle incorrecta: utilizar < en lugar de <= con límites inclusivos hace que se omita el último elemento restante. Segundo, una actualización incorrecta de los límites: olvidar +1 o -1 crea un bucle infinito cuando lo == hi. Tercero, operar sobre un arreglo no ordenado: la búsqueda binaria solo es correcta con datos ordenados.
Antes de escribir cualquier búsqueda binaria, diga en voz alta: «El arreglo está ordenado, mis límites son inclusivos y mi bucle se ejecuta mientras lo <= hi».
# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi: # should be lo <= hi for exact-match
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # stops, but never returns mid when found
return lo if arr[lo] == target else -1
print(buggy([1, 3, 5, 7], 7)) # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1)) # 0 (correct)
print(buggy([1, 3, 5, 7], 4)) # -1 (correct)Consejos para entrevistas sobre búsqueda binaria
Cuando vea un problema con un arreglo ordenado, una función monótona creciente o un espacio de búsqueda que se pueda dividir por la mitad, considere inmediatamente la búsqueda binaria. En una entrevista, explique su razonamiento: «Como el arreglo está ordenado, puedo descartar la mitad de los elementos en cada comparación, lo que proporciona O(log n)».
Verifique siempre su solución con al menos tres entradas: un valor al principio, un valor al final y un valor que no esté presente. Indicar proactivamente la complejidad —«tiempo O(log n), espacio O(1)»— antes de que se lo pregunten demuestra fundamentos sólidos.
Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Repaso de la lección
En esta lección aprendió que: la búsqueda binaria divide a la mitad el espacio de búsqueda en cada paso y requiere un tiempo de O(log n); la convención de límites inclusivos utiliza lo <= hi, con las actualizaciones lo = mid+1 y hi = mid-1; y para encontrar la primera o la última aparición, debe continuar buscando después de una coincidencia en lugar de devolver el resultado inmediatamente. A continuación, exploraremos cómo extender la búsqueda binaria a arreglos rotados y no ordenados.
Preguntas frecuentes
¿La lección «Búsqueda binaria clásica: izquierda, derecha y centro» es gratis?
Sí — el texto completo de «Búsqueda binaria clásica: izquierda, derecha y centro» 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 Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Búsqueda binaria clásica: izquierda, derecha y centro»?
Implemente la búsqueda binaria de forma iterativa y recursiva, domine los detalles de los desfases de uno en los límites lo/hi y compruebe la corrección con entradas límite. Practicas Coding Interview Prep 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 Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep 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: izquierda, derecha y centro»?
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 Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep 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: izquierda, derecha y centro
- Búsqueda binaria en arrays rotados y sin ordenar
- Límite inferior y límite superior
- Búsqueda binaria sobre el espacio de respuestas