Search in Rotated Sorted Array
Una lista de enteros distintos se ordenó en orden creciente y después se rotó: se tomaron algunos elementos del principio, posiblemente ninguno, y se movieron al final en el mismo orden. Por ejemplo, [2, 5, 8, 11, 15, 19, 23] rotada en 4 posiciones se convierte en [15, 19, 23, 2, 5, 8, 11]. Recibes la lista rotada nums y un entero target. Devuelve el índice de target en nums, contando desde 0, o -1 si no está, en tiempo O(log n).
Función
- numsinteger-array
- la lista ordenada y rotada de enteros distintos
- targetinteger
- el valor que se debe buscar
- Devuelveinteger
- el índice de target en nums, o -1 si no está
Restricciones
1 ≤ nums.length ≤ 5000-104 ≤ nums[i], target ≤ 104- Todos los valores de
numsson distintos. numses una lista creciente rotada por algúnkcon0 ≤ k < nums.length;k = 0la deja sin rotar.
Ejemplos
- Entrada
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- Salida
- 4
- Explicación
- 5 está en el índice 4. El primer elemento del medio, el índice 3, contiene 2, así que la mitad derecha
[2, 5, 8, 11]es la que está ordenada, y 5 está entre 2 y 11. El siguiente elemento del medio, el índice 5, contiene 8; la parte izquierda ordenada[5, 8]contiene 5, lo que lleva al índice 4.
- Entrada
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- Salida
- -1
- Explicación
- 65 estaría entre 60 y 70, y ningún elemento lo contiene. El primer elemento del medio, 70 en el índice 3, coloca 65 dentro de la parte izquierda ordenada
[40, 50, 60, 70]. El rango se reduce dentro de esa secuencia hasta quedar vacío, así que la función devuelve-1.
- Entrada
- nums = [8, 13, 21, 1, 3, 5]target = 13
- Salida
- 1
- Explicación
- El primer elemento central, índice 2, contiene 21. La parte izquierda
[8, 13, 21]está ordenada y 13 se encuentra entre 8 y 21, así que se descarta toda la parte derecha. Después, la búsqueda encuentra 13 en el índice 1.
+23 pruebas ocultas al enviar
Para ir más allá
Si nums puede contener duplicados, ningún algoritmo puede garantizar O(log n). ¿Puedes demostrarlo? Construye una lista rotada de 1 con un único 0 oculto en ella, donde cualquier búsqueda de 0 tenga que leer todos los elementos.
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Elige cualquier índice central y observa las dos mitades a cada lado. La rotación creó un punto donde los valores descienden, del mayor al menor. ¿Pueden ambas mitades contener ese descenso?
Al menos una mitad siempre está ordenada, y comparar
nums[lo]connums[mid]te indica cuál. Para una mitad ordenada, puedes comprobar en un solo paso sitargetestá entre su primer y su último valor.Mantén
loyhialrededor de la parte que todavía podría contenertarget. En cada paso, si el rango de valores de la mitad ordenada contienetarget, conserva esa mitad; de lo contrario, conserva la otra. Detente cuando encuentrestargeto el rango esté vacío.
Solución
Una lista ordenada y rotada consta de dos tramos ordenados colocados uno después del otro: [15, 19, 23] y después [2, 5, 8, 11]. La búsqueda binaria simple no funciona con ella, porque comparar target con el valor del medio ya no te indica en qué lado está target. La solución se basa en un hecho: dondequiera que cortes la lista, al menos una de las dos mitades está completamente ordenada, y en una mitad ordenada puedes determinar con una sola comparación si target puede estar dentro de ella.
Escanea cada elemento
Intuición
Comprueba cada índice en orden y devuelve el primero cuyo valor sea igual a target. Si el bucle termina sin encontrar ninguna coincidencia, devuelve -1. Los valores son distintos, así que la primera coincidencia es la única, y el recorrido es correcto para cualquier lista, esté rotada o no.
Ignora todo lo que te indica el problema. La lista está formada por dos tramos ordenados, pero el recorrido lee hasta los 5000 elementos, mientras que una búsqueda binaria necesita unas 13 comparaciones. La diferencia aumenta con el tamaño de la entrada: un millón de elementos requiere un millón de comparaciones, frente a unas 20. La tarea pide O(log n), así que este es el punto de partida que hay que mejorar, no la respuesta.
Algoritmo
- Para cada índice
idesde 0 hastan-1, comparanums[i]contarget. - Si son iguales, devuelve
i. - Después del bucle, devuelve
-1.
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1Encuentra el punto de rotación y después realiza una búsqueda binaria
Intuición
La lista rotada consta de dos tramos ordenados, y el segundo empieza por el valor más pequeño. Llama k a su índice. Una vez que conoces k, el problema se convierte en una búsqueda binaria sencilla: nums[k..n-1] está ordenado y contiene los valores desde nums[k] hasta nums[n-1], y nums[0..k-1] está ordenado y contiene todos los valores mayores. Una comparación de target con nums[k] y nums[n-1] permite elegir el tramo donde buscar.
Para encontrar k, haz una búsqueda binaria en el punto de descenso. Compara el valor del medio con el último valor del rango, nums[hi]. Si nums[mid] > nums[hi], los valores descienden en algún punto después de mid, así que el valor más pequeño está a su derecha: establece lo = mid + 1. De lo contrario, nums[mid..hi] asciende sin descensos, así que el valor más pequeño está en mid o antes: establece hi = mid, manteniendo mid dentro del rango. Cuando lo coincide con hi, ese índice es k.
Traza el primer ejemplo, [15, 19, 23, 2, 5, 8, 11] con target = 5. El 2 del medio no es mayor que 11, así que hi pasa a ser 3; después, 19 es mayor que 2, así que lo pasa a ser 2; después, 23 es mayor que 2, así que lo pasa a ser 3, y k = 3. Como 5 está entre nums[3] = 2 y nums[6] = 11, busca en los índices del 3 al 6, donde la búsqueda binaria encuentra 5 en el índice 4. Dos búsquedas binarias cuestan aproximadamente 2 log2 n pasos.
Algoritmo
- Establece
lo = 0yhi = n-1. Mientraslo < hi, calculamid; sinums[mid] > nums[hi], establecelo = mid + 1; de lo contrario, establecehi = mid. - Llama
kal índice final: contiene el valor más pequeño. - Si
nums[k] ≤ target ≤ nums[n-1], busca en los índices delkaln-1; de lo contrario, busca en los índices del 0 alk-1. - Ejecuta una búsqueda binaria simple en ese rango y devuelve el índice de
target, o-1si el rango queda vacío.
def search(nums, target):
n = len(nums)
# 1. Find k, the index of the smallest value, where the second run starts.
lo, hi = 0, n - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the drop is right of mid
else:
hi = mid # mid is in the low run: the minimum is at mid or left of it
k = lo
# 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
if nums[k] <= target <= nums[n - 1]:
lo, hi = k, n - 1
else:
lo, hi = 0, k - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Una búsqueda binaria en la mitad ordenada
Intuición
No necesitas saber dónde está el punto de rotación. Mantén la promesa habitual de la búsqueda binaria: si target está en la lista, su índice se encuentra entre lo y hi. Observa el índice central mid. Los valores solo disminuyen una vez en toda la lista, así que esa caída está en como máximo una de las dos mitades alrededor de mid, y la otra mitad está ordenada.
Encuentra la mitad ordenada con una comparación. Si nums[lo] ≤ nums[mid], la mitad izquierda nums[lo..mid] no tiene ninguna caída y está ordenada. Como ya sabes que nums[mid] no es target, target puede estar en esa mitad solo si nums[lo] ≤ target < nums[mid]. Si es así, establece hi = mid - 1; si no, target solo puede estar en la otra mitad, así que establece lo = mid + 1. Cuando nums[lo] > nums[mid], la caída está a la izquierda, la mitad derecha nums[mid..hi] está ordenada y decide la prueba simétrica nums[mid] < target ≤ nums[hi]. Nunca razonas directamente sobre la mitad desordenada: ahí es donde está target exactamente cuando no puede estar en la mitad ordenada.
Recorre el primer ejemplo, [15, 19, 23, 2, 5, 8, 11] con target = 5. El rango de 0 a 6 tiene como índice central 3, cuyo valor es 2. Como 15 es mayor que 2, la mitad derecha [2, 5, 8, 11] está ordenada y 5 está en ella, así que lo pasa a ser 4. El rango de 4 a 6 tiene como índice central 5, cuyo valor es 8. Ahora nums[4] = 5 ≤ 8; la mitad izquierda [5, 8] está ordenada y contiene 5, así que hi pasa a ser 4. En el índice 4 está el valor 5: devuelve 4.
En cada paso, el rango se reduce a la mitad, como en una búsqueda binaria normal, así que el bucle se ejecuta como máximo alrededor de log2(n) + 1 veces: 13 pasos para 5000 elementos, con dos índices de memoria adicional.
Algoritmo
- Establece
lo = 0yhi = n-1. - Mientras
lo ≤ hi, calculamid. Sinums[mid]es igual atarget, devuelvemid. - Si
nums[lo] ≤ nums[mid], la mitad izquierda está ordenada: sinums[lo] ≤ target < nums[mid], establecehi = mid - 1; de lo contrario, establecelo = mid + 1. - De lo contrario, la mitad derecha está ordenada: si
nums[mid] < target ≤ nums[hi], establecelo = mid + 1; de lo contrario, establecehi = mid - 1. - Cuando termine el bucle, devuelve
-1.
def search(nums, target):
lo, hi = 0, len(nums) - 1 # target, if present, sits in nums[lo..hi]
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
# nums[lo..mid] is sorted: target is in it only if it fits its range
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
# nums[mid..hi] is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
Errores comunes y casos límite
La búsqueda de una sola pasada es breve, y casi todos los errores se encuentran en un operador de comparación.
- Escribir
nums[lo] < nums[mid]en vez de≤. Cuando quedan dos elementos,mides igual alo, y la mitad izquierda tiene un elemento, que está ordenado. Con la prueba estricta,[9, 4]ytarget = 4consideran[9, 4]como la mitad derecha ordenada, buscan 4 fuera del intervalo de 9 a 4 y devuelven-1. - Comparar primero
targetconnums[mid], como en una búsqueda binaria normal. En[15, 19, 23, 2, 5, 8, 11]contarget = 19, el valor central 2 es menor que 19, así que la búsqueda avanza hacia la derecha y nunca encuentra el índice 1. - Comprobar solo un extremo de la mitad ordenada. En
[40, 50, 60, 70, 80, 10, 20]contarget = 80, el valor central es 70 y la mitad izquierda[40, 50, 60, 70]está ordenada. La comprobacióntarget ≥ nums[lo]por sí sola dirige la búsqueda hacia la izquierda, porque 80 es mayor que 40, pero 80 también es mayor que 70, así que está en la mitad derecha. Comprueba ambos extremos. - Olvidar el caso sin rotación en el enfoque de dos pasos. Cuando
k = 0, la segunda ejecución está vacía y su intervalo va de0a-1. Eso está bien con índices con signo, pero con índices sin signo (usizede Rust),k - 1desborda, por lo que el código de Rust usa intervalos semiabiertos. - Devolver la posición misma en Lua y R. Sus listas empiezan en 1, así que resta 1 antes de devolverla.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de buscar en un arreglo ordenado rotado?
Tiempo O(log n) y espacio extra O(1). Cada paso conserva una mitad del rango actual, igual que la búsqueda binaria simple, así que una lista de 5000 elementos necesita como máximo 13 pasos. La versión de dos pasos que encuentra primero el punto de rotación también es O(log n), con aproximadamente el doble de pasos.
¿Cómo sabes qué mitad de un arreglo rotado está ordenada?
Compara nums[lo] con nums[mid]. Los valores bajan solo una vez en toda la lista. Si nums[lo] ≤ nums[mid], ese descenso no está entre lo y mid, así que la mitad izquierda está ordenada. De lo contrario, el descenso está en la mitad izquierda, lo que significa que la mitad derecha, desde mid hasta hi, no tiene ninguno y está ordenada.
¿Funciona el algoritmo cuando el arreglo contiene duplicados?
No tal como está escrito. En [1, 0, 1, 1, 1], nums[lo], nums[mid] y nums[hi] son todos 1, así que no se puede demostrar que ninguna de las dos mitades esté ordenada. La solución habitual es avanzar lo una posición cuando nums[lo], nums[mid] y nums[hi] son iguales, lo que mantiene la respuesta correcta, pero hace que el peor caso sea O(n).
¿Deberías encontrar primero el punto de rotación o buscar en una sola pasada?
Ambos se ejecutan en O(log n). Encontrar primero el índice del mínimo divide el problema en dos búsquedas binarias simples, así que cada parte reutiliza código en el que ya confías. La búsqueda de una sola pasada hace lo mismo en un único bucle con menos pasos, y es la versión que esperan la mayoría de los entrevistadores.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def search(nums, target):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
Esperado
4