Find First and Last Position of Element in Sorted Array

Q: ¿Cuál es la complejidad temporal de encontrar la primera y la última posición?

Tiempo O(log n) y espacio O(1) , con dos búsquedas binarias. Ninguna se detiene al encontrar una coincidencia, así que el costo no depende de cuántas copias haya del objetivo: aproximadamente 14 pasos por búsqueda para 10^4 valores.

Q: ¿Qué es un límite inferior en la búsqueda binaria?

El límite inferior de un valor es el primer índice cuyo elemento es mayor o igual que ese valor, o la longitud de la lista si no existe ninguno. Es la posición en la que se insertaría el valor para mantener la lista ordenada. El límite superior es el primer índice cuyo elemento es estrictamente mayor.

Q: ¿Puede una función de búsqueda binaria encontrar tanto el primer índice como el último?

Sí. Dale a la búsqueda una bandera: cuando haya una coincidencia, registra el índice y sigue buscando hacia la izquierda para encontrar la primera copia, o hacia la derecha para encontrar la última. También funciona llamar a una búsqueda de límite inferior con target y con target + 1 . Ambas se ejecutan en O(log n) .

MedioBúsqueda binaria

+10

Recibes una lista de enteros nums ordenada en orden no decreciente, por lo que un valor puede repetirse, y un entero target. Devuelve una lista de dos índices, empezando a contar desde 0: la primera y la última posición donde aparece target. Si target no está en la lista, devuelve [-1, -1]. Intenta lograr un tiempo de O(log n).

Función

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

numsinteger-array: la lista ordenada de números enteros, que puede contener valores repetidos
targetinteger: el valor que se debe buscar
Devuelveinteger-array: el primer y el último índice de target, o [-1, -1] si no está

Restricciones

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums está ordenado en orden no decreciente.

Ejemplos

Entrada: nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
Salida: [1, 3]
Explicación: Las tres copias de 5 están en los índices 1, 2 y 3, así que la secuencia empieza en 1 y termina en 3. El índice 0 contiene 3 y el índice 4 contiene 8, así que la secuencia no puede extenderse más.

Entrada: nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
Salida: [-1, -1]
Explicación: 7 se situaría entre 5 en el índice 3 y 8 en el índice 4, y ninguno de los dos es 7. La lista no contiene ninguna copia, así que la respuesta es [-1, -1].

Para ir más allá

Si la misma lista recibe miles de consultas para distintos objetivos, ¿puede una pasada por adelantado hacer que cada consulta sea más rápida que O(log n)?

Pistas

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

0 de 3 abiertas

Solución

Una búsqueda binaria simple se detiene en la copia de target con la que se encuentra, y esa copia puede estar en cualquier lugar de la secuencia. Busca un límite inferior en su lugar: el primer índice cuyo valor sea al menos un número determinado. Los límites inferiores de target y target + 1 dan ambos extremos de la secuencia en O(log n).

Revisa toda la lista

Intuición

Recorre la lista una vez. El primer índice que contiene target es el inicio y el último es el final. Si target nunca aparece, ambos se quedan en -1.

Esto funciona con cualquier lista, ordenada o no, y esa es su debilidad: lee los n valores. Una lista de 10^4 valores requiere 10 000 comparaciones, cuando bastarían unas 28.

Algoritmo

Establece first = last = -1.
Para cada índice i, si nums[i] es igual a target, establece first = i cuando first siga siendo -1, y establece last = i.
Devuelve [first, last].

def searchRange(nums, target):
    first = last = -1
    for i, value in enumerate(nums):
        if value == target:
            if first == -1:
                first = i  # the first match fixes the start
            last = i  # every later match moves the end
    return [first, last]

Encuentra una copia y después expándela

Intuición

Realiza una búsqueda binaria para encontrar cualquier índice que contenga target. La lista está ordenada, así que todas las copias se encuentran en una secuencia continua alrededor de ese índice: avanza hacia la izquierda y hacia la derecha mientras el vecino siga siendo target.

La búsqueda cuesta O(log n) y el recorrido, un paso por copia: k en total. Cuando la mayor parte de la lista es target, por ejemplo, 10^4 copias, el recorrido lee todos los valores y vuelves a una búsqueda lineal.

Algoritmo

Busca cualquier índice found mediante búsqueda binaria, de modo que nums[found] == target.
Si no hay ninguno, devuelve [-1, -1].
Mueve first hacia la izquierda desde found mientras el valor anterior sea igual a target.
Mueve last hacia la derecha desde found mientras el valor siguiente sea igual a target.
Devuelve [first, last].

def searchRange(nums, target):
    # An ordinary binary search finds some copy of target, if there is one.
    lo, hi = 0, len(nums) - 1
    found = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            found = mid
            break
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    if found == -1:
        return [-1, -1]
    # The copies sit next to each other, so walk out to both ends of the run.
    first = last = found
    while first > 0 and nums[first - 1] == target:
        first -= 1
    while last < len(nums) - 1 and nums[last + 1] == target:
        last += 1
    return [first, last]

Dos búsquedas binarias con límite inferior

Intuición

Plantea una pregunta diferente: ¿cuál es el primer índice cuyo valor es al menos value? Ese índice es el límite inferior, o n si ningún valor cumple la condición. Mantén un intervalo semiabierto [lo, hi) que siempre lo contenga. Si nums[mid] < value, entonces mid y todo lo que está antes son demasiado pequeños. De lo contrario, mid cumple la condición, pero también podría cumplirla un índice anterior, así que mid permanece en el intervalo como el nuevo hi. El bucle nunca se detiene antes de tiempo al encontrar una coincidencia.

El límite inferior de target es donde empieza su secuencia. Los valores son enteros, así que el primer valor mayor que target se encuentra en el límite inferior de target + 1, y la secuencia termina un índice antes. En el primer ejemplo, el límite inferior de 5 es 1 y el límite inferior de 6 es 4, donde se encuentra el 8: la secuencia es [1, 3]. Las dos búsquedas requieren unos 28 pasos para 10^4 valores, independientemente de la longitud de la secuencia.

Algoritmo

Escribe lowerBound(value): comienza con lo = 0, hi = n; mientras lo < hi, si nums[mid] < value, establece lo = mid + 1; de lo contrario, establece hi = mid; devuelve lo.
Establece first = lowerBound(target).
Si first == n o nums[first] != target, devuelve [-1, -1].
Establece last = lowerBound(target + 1) - 1 y devuelve [first, last].

def lowerBound(nums, value):
    # The first index whose number is at least value, or len(nums) if none is.
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < value:
            lo = mid + 1  # nums[mid] and everything before it is too small
        else:
            hi = mid  # nums[mid] qualifies, but an earlier index might too
    return lo


def searchRange(nums, target):
    first = lowerBound(nums, target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    # The run of target ends right before the first number above target.
    last = lowerBound(nums, target + 1) - 1
    return [first, last]

Errores comunes y casos límite

Devolver el resultado en cuanto nums[mid] == target. Ese índice puede estar en cualquier lugar del tramo: en [3, 5, 5, 5, 8], el primer elemento del medio está en el índice 2, que no es ninguno de los extremos.
Escribir hi = mid - 1 en la búsqueda del límite inferior cuando nums[mid] ≥ value. Eso descarta mid, que podría ser la respuesta.
Leer nums[first] sin comprobar first < n. Cuando target es mayor que todos los valores, como lo sería 13 en los ejemplos, el límite inferior es n, una posición después del final.
Olvidar el desplazamiento en Lua y R. Sus listas empiezan en 1, así que resta 1 a ambas posiciones.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de encontrar la primera y la última posición?

Tiempo O(log n) y espacio O(1), con dos búsquedas binarias. Ninguna se detiene al encontrar una coincidencia, así que el costo no depende de cuántas copias haya del objetivo: aproximadamente 14 pasos por búsqueda para 10^4 valores.

¿Qué es un límite inferior en la búsqueda binaria?

El límite inferior de un valor es el primer índice cuyo elemento es mayor o igual que ese valor, o la longitud de la lista si no existe ninguno. Es la posición en la que se insertaría el valor para mantener la lista ordenada. El límite superior es el primer índice cuyo elemento es estrictamente mayor.

¿Puede una función de búsqueda binaria encontrar tanto el primer índice como el último?

Sí. Dale a la búsqueda una bandera: cuando haya una coincidencia, registra el índice y sigue buscando hacia la izquierda para encontrar la primera copia, o hacia la derecha para encontrar la última. También funciona llamar a una búsqueda de límite inferior con target y con target + 1. Ambas se ejecutan en O(log n).

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

Prueba #1

Prueba #2

Argumentos

nums = [3, 5, 5, 5, 8, 9, 9, 12]
target = 5

Salida Esperada

[1, 3]

Find First and Last Position of Element in Sorted Array

Función

Restricciones

Ejemplos

Pistas

Solución

Revisa toda la lista

Encuentra una copia y después expándela

Dos búsquedas binarias con límite inferior

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares