Binary Search
Se te proporciona una lista de números enteros nums ordenados de menor a mayor, sin valores repetidos, y un número entero target. Devuelve el índice de target en nums, empezando a contar desde 0, o -1 si no está en la lista. Intenta lograr un tiempo de ejecución de O(log n), lo que significa que no puedes permitirte revisar todos los elementos.
Función
- numsinteger-array
- la lista ordenada de números enteros distintos
- targetinteger
- el valor que se debe buscar
- Devuelveinteger
- el índice de target en nums, o -1 si no se encuentra
Restricciones
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsestá ordenado en orden estrictamente creciente, por lo que cada valor aparece una sola vez.
Ejemplos
- Entrada
- nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
- Salida
- 4
- Explicación
nums[4]es 9. La búsqueda mira el índice 3 (valor 4, demasiado pequeño), después el índice 5 (valor 15, demasiado grande) y, por último, el índice 4, donde encuentra 9.
- Entrada
- nums = [1, 3, 5, 8, 13, 21]target = 10
- Salida
- -1
- Explicación
- 10 estaría entre 8 y 13, y ninguno de los dos es 10, así que no está en la lista. El rango de búsqueda se reduce hasta que
losobrepasahi, y la función devuelve-1.
+15 pruebas ocultas al enviar
Para ir más allá
Si nums pudiera contener valores repetidos, ¿cómo devolverías el primer índice de target, manteniendo O(log n)?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
La lista está ordenada. Si comparas
targetcon un elemento del medio, ¿qué te dice eso sobre todos los elementos que están a un lado?Si
nums[mid] < target, entoncesnums[mid]y todo lo que está a su izquierda es demasiado pequeño, así quetargetsolo puede estar a la derecha. Una comparación descarta la mitad de los candidatos.Mantén dos índices,
loyhi, alrededor de la parte de la lista que todavía podría contenertarget. Compara con el elemento del medio, mueveloohimás allá de él y detente cuando encuentrestargeto cuandolosobrepasehi.
Solución
Leer los elementos uno por uno permite encontrar target, pero ignora el hecho que hace interesante el problema: la lista está ordenada. Una sola comparación con el elemento del medio te indica qué mitad todavía puede contener target, así que puedes descartar la mitad de los candidatos en cada paso. Una lista de 10^4 elementos necesita después como máximo 14 comparaciones en lugar de 10000.
Escanea de izquierda a derecha
Intuición
Comprueba cada índice en orden y devuelve el primero cuyo valor sea igual a target. Si el bucle termina sin encontrar una coincidencia, target no está en la lista, así que devuelve -1. Cada elemento se compara una vez, lo que hace que la respuesta sea correcta para cualquier lista, esté ordenada o no.
El problema es esa generalidad. Una lista de 10^4 elementos requiere hasta 10000 comparaciones, y el trabajo crece al mismo ritmo que n. El recorrido nunca aprovecha que nums está ordenada, así que no alcanza el límite de O(log n) que pide la tarea. Podrías detenerte antes cuando un valor supere target, pero en el peor de los casos sigues leyendo toda la lista.
Algoritmo
- Para cada índice
ide 0 an-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 -1Búsqueda binaria con dos índices
Intuición
Mantén dos índices, lo y hi, con una promesa: si target está en la lista, su índice se encuentra entre lo y hi, inclusive. Al principio, ese rango abarca toda la lista, de 0 a n-1. Mira el índice central mid. Si nums[mid] es igual a target, ya terminaste. Si es menor, como la lista está ordenada, todos los elementos hasta mid también son menores, así que mueve lo a mid + 1. Si es mayor, mueve hi a mid - 1. La promesa sigue cumpliéndose después de cualquiera de los dos movimientos.
Sigue el primer ejemplo, [-7, -2, 0, 4, 9, 15, 23] con target = 9. El rango de 0 a 6 tiene como índice central el 3, cuyo valor es 4, demasiado pequeño, así que el rango pasa a ser de 4 a 6. Su índice central es el 5, que contiene 15, demasiado grande, así que el rango pasa a ser de 4 a 4. El índice 4 contiene 9: devuelve 4.
Si target no está, el rango se reduce hasta que lo supera a hi. El rango queda vacío; la promesa indica entonces que target no está en ninguna parte, y devuelves -1. Cada paso reduce el rango a la mitad, así que el bucle se ejecuta como máximo unas log2(n) + 1 veces: 14 pasos para 10^4 elementos. Dos índices son todo el espacio de memoria adicional que necesitas.
Algoritmo
- Establece
lo = 0yhi = n-1. - Mientras
lo ≤ hi, calculamid = lo + (hi - lo) / 2. - Si
nums[mid]es igual atarget, devuelvemid. - Si
nums[mid] < target, 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[mid] < target:
lo = mid + 1 # nums[mid] and everything left of it is too small
else:
hi = mid - 1 # nums[mid] and everything right of it is too big
return -1
Errores comunes y casos límite
La búsqueda binaria es breve, y casi todos los errores son desfases de una unidad en los extremos del rango.
- Usar un bucle con
lo < hicuandohiempieza en el último índice. El bucle se detiene cuando aún queda un candidato sin comprobar, así quenums = [5]contarget = 5devuelve-1. Con un rango inclusivo, usa el bucle mientraslo ≤ hi. - Actualizar
lo = midohi = midcon un rango inclusivo. Cuandoloyhison contiguos,mides igual aloy el rango nunca se reduce: se produce un bucle infinito. Ya comprobastenums[mid], así que avanza más allá conmid + 1omid - 1. - Calcular
(lo + hi) / 2con un entero de ancho fijo. La suma desborda cuando los índices superan aproximadamente10^9. Los límites aquí están muy por debajo de eso, perolo + (hi - lo) / 2es el hábito seguro. - Devolver
locuando faltatarget. Después del bucle,loes el punto de inserción, que es un índice válido, no-1. - Olvidar el desplazamiento en Lua y R. Sus listas empiezan en 1, así que el índice que devuelves es la posición menos 1.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de la búsqueda binaria?
O(log n). Cada comparación reduce a la mitad el rango que todavía puede contener el objetivo, así que después de k pasos quedan como máximo n / 2^k candidatos. Una lista de 10^4 elementos necesita como máximo 14 comparaciones, y una lista de 10^9 elementos, como máximo 30. La versión iterativa usa O(1) de espacio adicional.
¿Por qué la búsqueda binaria necesita un arreglo ordenado?
El paso que descarta la mitad de la lista depende del orden. Cuando nums[mid] < target, la ordenación garantiza que todos los elementos a la izquierda de mid también son menores que target, así que ninguno puede coincidir. En una lista desordenada, esa comparación no dice nada sobre los demás elementos y tienes que revisarlos todos.
¿La búsqueda binaria debe ser iterativa o recursiva?
Ambas son correctas y ambas se ejecutan en tiempo O(log n). La versión recursiva se llama a sí misma con una de las mitades y usa O(log n) de espacio en la pila; la versión iterativa mueve lo y hi en un bucle y usa O(1). En las entrevistas, normalmente esperan el bucle, y este evita cualquier límite de recursión.
¿Cómo evitas el desbordamiento al calcular el índice medio?
Escribe mid = lo + (hi - lo) / 2 en lugar de (lo + hi) / 2. Ambas formas dan el mismo índice, pero la segunda suma primero dos índices y, con un entero de 32 bits, esa suma se desborda cuando los índices superan aproximadamente 1.07 × 10^9. Python y Ruby tienen enteros ilimitados, así que allí la forma abreviada es segura.
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
Entrada
nums = [-7, -2, 0, 4, 9, 15, 23] target = 9
Esperado
4