Search in Rotated Sorted Array

Q: ¿Cuál es la complejidad temporal de buscar en un arreglo ordenado y rotado?

Tiempo O(log n) y espacio adicional O(1) . Cada paso conserva una mitad del rango, así que 5000 elementos necesitan como máximo 13 pasos. Encontrar primero el punto de rotación también es O(log n) , con aproximadamente el doble de pasos.

Q: ¿Funciona el algoritmo cuando el array contiene duplicados?

No tal como está escrito. Cuando nums[lo] , nums[mid] y nums[hi] son iguales, no se puede demostrar que ninguna de las dos mitades esté ordenada. La solución habitual adelanta lo una posición en ese caso, lo que mantiene la respuesta correcta, pero hace que el peor caso sea O(n) .

Q: ¿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 mínimo divide el problema en dos búsquedas binarias simples. La búsqueda de una sola pasada hace el trabajo en un único bucle con menos pasos, y es la versión que esperan la mayoría de los entrevistadores.

MedioBúsqueda binaria

+10

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 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

search(nums: integer-array, target: integer) → integer

numsinteger-array: la lista rotada y ordenada de números 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
-10⁴ ≤ nums[i], target ≤ 10⁴
Todos los valores de nums son distintos.
nums es una lista creciente rotada por algún k con 0 ≤ k < nums.length; k = 0 la deja sin rotar.

Ejemplos

Entrada: nums = [15, 19, 23, 2, 5, 8, 11]target = 5
Salida: 4
Explicación: El primer elemento central, índice 3, contiene 2, así que la mitad derecha [2, 5, 8, 11] está ordenada y contiene 5. El siguiente elemento central, í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 pertenecería entre 60 y 70, y ningún elemento lo contiene. El primer elemento central, 70, sitúa 65 dentro de la parte izquierda ordenada [40, 50, 60, 70], y el rango se reduce allí hasta quedar vacío.

Entrada: nums = [8, 13, 21, 1, 3, 5]target = 13
Salida: 1
Explicación: El primer elemento central, el índice 2, contiene 21. La parte izquierda [8, 13, 21] está ordenada y 13 se encuentra entre 8 y 21, así que se descarta la parte derecha. Después, la búsqueda encuentra 13 en el índice 1.

Para ir más allá

Si nums puede contener duplicados, ningún algoritmo puede garantizar O(log n). ¿Puedes demostrarlo con una lista rotada de 1 que oculta un único 0?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Una lista ordenada rotada consta de dos tramos ordenados: [15, 19, 23] y después [2, 5, 8, 11]. Comparar target con el valor del medio ya no te indica en qué lado se encuentra. Pero, dondequiera que cortes la lista, al menos una mitad está ordenada, y una comparación te indica si target puede estar en esa mitad.

Escanea cada elemento

Intuición

Comprueba cada índice y devuelve el primero cuyo valor sea igual a target, o -1 después del bucle. Lee todos los elementos, así que es correcto para cualquier lista. Ignora los dos tramos ordenados: 5000 elementos requieren hasta 5000 comparaciones, mientras que una búsqueda binaria necesita 13.

Algoritmo

Para cada índice i desde 0 hasta n-1, compara nums[i] con target.
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 -1

Encuentra el punto de rotación y después realiza una búsqueda binaria

Intuición

El segundo tramo comienza en el valor más pequeño; llama k a su índice. Tanto nums[k..n-1] como nums[0..k-1] están ordenados, y todos los valores del primer tramo son mayores que todos los del segundo. Una vez que conoces k, comparar target con nums[k] y nums[n-1] permite elegir el tramo, y una búsqueda binaria normal lo termina.

Para encontrar k, compara el valor del medio con nums[hi]. Si nums[mid] > nums[hi], los valores descienden en algún punto después de mid, así que el mínimo está a su derecha. De lo contrario, nums[mid..hi] asciende sin descensos, así que el mínimo está en mid o antes. En el primer ejemplo, los valores del medio son 2, 19 y 23, lo que da k = 3, y 5 está entre nums[3] = 2 y nums[6] = 11. Dos búsquedas binarias cuestan aproximadamente 2 log2 n pasos.

Algoritmo

Establece lo = 0 y hi = n-1. Mientras lo < hi, calcula mid; si nums[mid] > nums[hi], establece lo = mid + 1; de lo contrario, establece hi = mid.
El índice final k contiene el valor más pequeño.
Si nums[k] ≤ target ≤ nums[n-1], realiza una búsqueda binaria en los índices k a n-1; de lo contrario, busca de 0 a k-1.
Devuelve el índice encontrado, o -1 si 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 -1

Una búsqueda binaria en la mitad ordenada

Intuición

Mantén la promesa de la búsqueda binaria: si target está en la lista, su índice se encuentra entre lo y hi. Los valores disminuyen solo una vez en toda la lista, así que como máximo una de las dos mitades alrededor de mid contiene la disminución, y la otra está ordenada. Si nums[lo] ≤ nums[mid], la mitad izquierda está ordenada; de lo contrario, lo está la derecha.

Para la mitad ordenada, una prueba del rango en sus dos extremos indica si target puede estar dentro; por ejemplo, nums[lo] ≤ target < nums[mid] en la mitad izquierda. Si puede estar, busca allí; si no, target solo puede estar en la otra mitad. En cada paso, el rango se reduce a la mitad: como máximo 13 pasos para 5000 elementos.

Algoritmo

Establece lo = 0 y hi = n-1.
Mientras lo ≤ hi, calcula mid y devuélvelo si nums[mid] es igual a target.
Si nums[lo] ≤ nums[mid], la mitad izquierda está ordenada: establece hi = mid - 1 cuando nums[lo] ≤ target < nums[mid]; de lo contrario, establece lo = mid + 1.
De lo contrario, la mitad derecha está ordenada: establece lo = mid + 1 cuando nums[mid] < target ≤ nums[hi]; de lo contrario, establece hi = 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

Escribir nums[lo] < nums[mid] en lugar de ≤. Cuando quedan dos elementos, mid es igual a lo, y la prueba estricta considera [9, 4] una mitad derecha ordenada: target = 4 devuelve -1.
Comparar target con nums[mid] primero. En el primer ejemplo, con target = 19, el 2 del medio es menor, así que la búsqueda avanza hacia la derecha y no encuentra el índice 1.
Comprobar solo un extremo de la mitad ordenada. En [40, 50, 60, 70, 80, 10, 20], con target = 80, target ≥ nums[lo] por sí solo envía la búsqueda a [40, 50, 60, 70].
En Rust, k - 1 con un usize produce un desbordamiento cuando k = 0, es decir, en la lista sin rotar. Usa rangos semiabiertos.
En Lua y R, devolver la posición basada en 1. Resta 1.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de buscar en un arreglo ordenado y rotado?

Tiempo O(log n) y espacio adicional O(1). Cada paso conserva una mitad del rango, así que 5000 elementos necesitan como máximo 13 pasos. Encontrar primero el punto de rotación también es O(log n), con aproximadamente el doble de pasos.

¿Funciona el algoritmo cuando el array contiene duplicados?

No tal como está escrito. Cuando nums[lo], nums[mid] y nums[hi] son iguales, no se puede demostrar que ninguna de las dos mitades esté ordenada. La solución habitual adelanta lo una posición en ese caso, 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 mínimo divide el problema en dos búsquedas binarias simples. La búsqueda de una sola pasada hace el trabajo en un único bucle con menos pasos, y es la versión que esperan la mayoría de los entrevistadores.

def search(nums, target):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

nums = [15, 19, 23, 2, 5, 8, 11]
target = 5

Salida Esperada

Search in Rotated Sorted Array

Función

Restricciones

Ejemplos

Pistas

Solución

Escanea cada elemento

Encuentra el punto de rotación y después realiza una búsqueda binaria

Una búsqueda binaria en la mitad ordenada

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares