Búsqueda binaria en arrays rotados y sin ordenar
Resuelva search-in-rotated-sorted-array y find-minimum-in-rotated-array determinando qué mitad está ordenada en cada paso.
Búsqueda binaria en arrays rotados y sin ordenar es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 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.
¿Qué es un arreglo ordenado rotado?
Un arreglo ordenado rotado es un arreglo ordenado que se ha cortado en algún pivote y cuyas dos partes se han intercambiado. Por ejemplo, [4, 5, 6, 7, 0, 1, 2] es el arreglo ordenado [0,1,2,4,5,6,7] rotado en el índice 4. La búsqueda binaria estándar falla aquí porque el arreglo ya no está ordenado globalmente.
La idea fundamental es que al menos una mitad del arreglo siempre está ordenada después de cualquier rotación. La búsqueda binaria debe identificar qué mitad está ordenada antes de decidir cómo mover los límites.
# A rotated sorted array — one half is always sorted
arr = [4, 5, 6, 7, 0, 1, 2]
# Left half [4,5,6,7] is sorted
# Right half [0,1,2] is also sorted
# But left[0]=4 > right[-1]=2 => rotation happened in left-to-right crossingIdentificar la mitad ordenada
Después de calcular mid, compare arr[lo] con arr[mid]. Si arr[lo] <= arr[mid], la mitad izquierda está ordenada; de lo contrario, la mitad derecha está ordenada. Una vez que sepa qué mitad está ordenada, puede comprobar si el objetivo se encuentra dentro de ese rango ordenado y acotar la búsqueda en consecuencia.
Este árbol de decisiones permite descartar exactamente la mitad del array en cada paso, manteniendo la complejidad O(log n) incluso en un array rotado.
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3)) # -1Recorrer un ejemplo paso a paso
Recorramos search_rotated([4,5,6,7,0,1,2], 0) paso a paso. Inicialmente, lo=0, hi=6, mid=3, arr[mid]=7. ¿Se encuentra el objetivo 0 en la mitad izquierda ordenada [4..7]? No, así que movemos lo=4. Ahora, lo=4, hi=6, mid=5, arr[mid]=1. La mitad izquierda [0,1] está ordenada (arr[lo]=0 <= arr[mid]=1). ¿Está 0 en [0..1)? Sí, así que establecemos hi=4. Ahora, lo=4, hi=4, mid=4, arr[4]=0; se encontró en el índice 4.
# Step-by-step trace
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
steps = []
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
steps.append(f'lo={lo} hi={hi} mid={mid} val={nums[mid]}')
if nums[mid] == target:
steps.append(f'Found at {mid}')
break
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
for s in steps:
print(s)Gestionar duplicados en la rotación
Cuando el array rotado puede contener duplicados (por ejemplo, [1,3,1,1,1]), la condición nums[lo] == nums[mid] es ambigua: no puede determinar qué mitad está ordenada. La solución segura consiste en incrementar lo (o decrementar hi) en uno y volver a intentarlo. Esto degrada el tiempo en el peor caso a O(n), algo que debe mencionar al entrevistador.
def search_rotated_with_dups(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return True
# Ambiguous: shrink left boundary
if nums[lo] == nums[mid] == nums[hi]:
lo += 1
hi -= 1
elif nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return False
print(search_rotated_with_dups([1, 3, 1, 1, 1], 3)) # True
print(search_rotated_with_dups([2, 2, 2, 0, 2], 0)) # TrueEncontrar el mínimo en un array ordenado rotado
Un problema relacionado consiste en encontrar el elemento mínimo en un array ordenado rotado sin buscar un objetivo específico. El mínimo siempre se encuentra en la mitad no ordenada. En cada paso: si arr[mid] > arr[hi], el mínimo está en la mitad derecha (lo = mid + 1); de lo contrario, está en la mitad izquierda, incluido mid (hi = mid). Cuando lo == hi, habrá encontrado el mínimo.
def find_min(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # min is in right half
else:
hi = mid # min is at mid or left of mid
return nums[lo]
print(find_min([3, 4, 5, 1, 2])) # 1
print(find_min([4, 5, 6, 7, 0, 1, 2])) # 0
print(find_min([11, 13, 15, 17])) # 11 (no rotation)Por qué arr[lo] <= arr[mid] detecta la mitad izquierda ordenada
La condición arr[lo] <= arr[mid] funciona porque, en un segmento ordenado (o ordenado sin rotación), el primer elemento siempre es el menor. Si arr[lo] <= arr[mid], no se produjo ninguna rotación dentro de [lo..mid], por lo que esa mitad está ordenada. La igualdad contempla el caso en que lo == mid (un segmento de un solo elemento está ordenado de forma trivial).
Por el contrario, si arr[lo] > arr[mid], el pivote de rotación debe encontrarse entre lo y mid, lo que significa que la mitad derecha [mid..hi] es el segmento ordenado contiguo.
# Visualise: detect which half is sorted
examples = [
([4, 5, 6, 7, 0, 1, 2], 0, 6), # mid=3, val=7 => left sorted
([6, 7, 0, 1, 2, 4, 5], 0, 6), # mid=3, val=1 => right sorted
]
for arr, lo, hi in examples:
mid = lo + (hi - lo) // 2
if arr[lo] <= arr[mid]:
print(f'arr[{lo}]={arr[lo]} <= arr[{mid}]={arr[mid]} => LEFT half sorted')
else:
print(f'arr[{lo}]={arr[lo]} > arr[{mid}]={arr[mid]} => RIGHT half sorted')Análisis de complejidad
Buscar en un array ordenado rotado mediante búsqueda binaria sigue teniendo un tiempo de O(log n) y un espacio de O(1), porque seguimos dividiendo por la mitad el espacio de búsqueda en cada iteración. La única diferencia respecto a la búsqueda binaria clásica es una comprobación adicional de tiempo constante para identificar qué mitad está ordenada.
Con duplicados, el peor caso se degrada a O(n), porque es posible que solo incrementemos lo en uno en cada paso. Mencione explícitamente esta compensación: demuestra que tiene en cuenta los casos límite más allá del caso favorable.
Recorrido de LeetCode 33
LeetCode 33 'Search in Rotated Sorted Array' es la forma canónica de este problema. Las restricciones garantizan que no hay duplicados y que existe exactamente una rotación. La solución es la función search_rotated que escribimos antes. Puntos clave para la entrevista: indique siempre la suposición de que no hay duplicados, verifique las desigualdades con un ejemplo concreto en el límite y confirme que el índice devuelto es correcto tanto cuando se encuentra el objetivo como cuando no se encuentra.
# LeetCode 33 — complete solution
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
# Tests
print(search([4,5,6,7,0,1,2], 0)) # 4
print(search([4,5,6,7,0,1,2], 3)) # -1
print(search([1], 0)) # -1LeetCode 153: Encontrar el mínimo sin duplicados
LeetCode 153 'Find Minimum in Rotated Sorted Array' solicita encontrar el mínimo sin duplicados. El enfoque consiste en comparar arr[mid] con arr[hi] (no con arr[lo]) para determinar en qué lado se encuentra el mínimo. Si arr[mid] > arr[hi], el mínimo está a la derecha; de lo contrario, está en mid o a la izquierda. Este proceso converge al mínimo en O(log n).
def findMin(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]
print(findMin([3,4,5,1,2])) # 1
print(findMin([4,5,6,7,0,1,2])) # 0
print(findMin([11,13,15,17])) # 11Recuento de rotaciones e índice del pivote
Una vez que puede encontrar el elemento mínimo, también conoce el número de rotaciones: el índice del mínimo es exactamente el número de posiciones que el array se rotó hacia la derecha. Por ejemplo, en [4,5,6,7,0,1,2], el mínimo está en el índice 4, por lo que el array se rotó 4 posiciones.
Conocer el pivote permite aplicar una búsqueda binaria estándar tratando los índices mediante módulo n: real_idx = (mid + pivot) % n. Esta formulación alternativa puede simplificar el razonamiento al trabajar con estructuras indexadas de forma circular.
def search_via_pivot(nums, target):
n = len(nums)
# Find pivot (index of minimum)
lo, hi = 0, n - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
pivot = lo
# Binary search with offset
lo, hi = 0, n - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
real_mid = (mid + pivot) % n
if nums[real_mid] == target:
return real_mid
elif nums[real_mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_via_pivot([4,5,6,7,0,1,2], 0)) # 4Integrarlo todo
Cuando se encuentre con un problema de arrays rotados en una entrevista, siga este árbol de decisiones. Primero, determine si necesita encontrar un objetivo o encontrar el mínimo. Para encontrar un objetivo, use el enfoque de identificación de la mitad ordenada. Para encontrar el mínimo, compare mid con hi. Si puede haber duplicados, mencione el peor caso O(n) y añada la alternativa de reducir los límites.
Practique recorriendo su código con los tres ejemplos clásicos: sin rotación, rotado una vez y rotado de modo que el mínimo quede en la última posición.
Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que: un array ordenado rotado siempre tiene al menos una mitad ordenada, debe comparar arr[lo] con arr[mid] para identificar qué mitad está ordenada antes de decidir dónde buscar y para encontrar el mínimo se usa arr[mid] frente a arr[hi] con el fin de localizar el pivote de rotación. A continuación, exploraremos las variantes de búsqueda binaria de cota inferior y cota superior.
Preguntas frecuentes
¿La lección «Búsqueda binaria en arrays rotados y sin ordenar» es gratis?
Sí — el texto completo de «Búsqueda binaria en arrays rotados y sin ordenar» 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 en arrays rotados y sin ordenar»?
Resuelva search-in-rotated-sorted-array y find-minimum-in-rotated-array determinando qué mitad está ordenada en cada paso. 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 2 de 4.
¿Cuánto tiempo toma la lección «Búsqueda binaria en arrays rotados y sin ordenar»?
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