Límite inferior y límite superior

La cota inferior de un valor objetivo en un array ordenado es el índice del primer elemento mayor o igual que el objetivo (a menudo se denomina bisect_left). La cota superior es el índice del primer elemento estrictamente mayor que el objetivo (bisect_right). Juntas delimitan todas las apariciones del objetivo y permiten realizar consultas de rangos en O(log n).

Estas dos operaciones son la base de muchos problemas de entrevistas: contar apariciones, encontrar rangos, determinar posiciones de inserción y mucho más.

bisect_left(arr, x) devuelve el índice más a la izquierda i tal que arr[i] >= x, o len(arr) si todos los elementos son menores. La implementación usa un límite superior exclusivo: hi = len(arr), la condición del bucle lo < hi y la actualización hi = mid cuando arr[mid] >= x. Esto garantiza que la respuesta converja a la primera posición válida.

bisect_right(arr, x) devuelve el índice más a la izquierda i tal que arr[i] > x. Solo cambia una línea respecto a bisect_left: la condición cambia de arr[mid] < x a arr[mid] <= x. Cuando arr[mid] <= x, la respuesta está estrictamente a la derecha de mid, por lo que establecemos lo = mid + 1; de lo contrario, acotamos desde la derecha.

Para contar las apariciones de un objetivo en un array ordenado en O(log n), aplique ambas cotas: count = bisect_right(arr, target) - bisect_left(arr, target). Si el recuento es 0, el objetivo no está presente. Esto es considerablemente más rápido que un recorrido lineal y constituye el enfoque estándar para las consultas de frecuencia sobre datos ordenados.

LeetCode 34 'Find First and Last Position of Element in Sorted Array' solicita devolver [first_idx, last_idx] en O(log n). La primera posición es bisect_left(arr, target), pero solo si arr[result] == target. La última posición es bisect_right(arr, target) - 1. Si alguna de las comprobaciones falla, devuelva [-1, -1].

LeetCode 35 'Search Insert Position' plantea la siguiente pregunta: ¿dónde se insertaría el objetivo para mantener el array ordenado? Esto es exactamente bisect_left(arr, target). Si el objetivo existe, bisect_left devuelve su índice. Si no existe, bisect_left devuelve el índice donde se insertaría. No se necesita ningún tratamiento especial: la misma función gestiona ambas situaciones.

Cuando no existen duplicados, bisect_left y bisect_right devuelven el mismo índice. La diferencia solo importa cuando el objetivo aparece varias veces. bisect_left señala la primera ocurrencia; bisect_right señala la posición posterior a la última ocurrencia. Elija siempre una u otra según necesite insertar antes de las ocurrencias existentes (izquierda) o después de ellas (derecha).

Cuando necesite responder de forma eficiente a muchas consultas de frecuencia por rangos sobre un array ordenado, ordene el array una sola vez y use bisect para cada consulta. Cada consulta responde a «¿cuántos elementos se encuentran en [lo, hi]?» en O(log n), en lugar de O(n). Este patrón aparece en problemas sobre el recuento de elementos dentro de un rango de valores después de ordenar.

A veces, la clave de búsqueda no es el valor almacenado, sino una propiedad derivada. El módulo bisect de Python no admite directamente una función de clave, pero puede realizar la búsqueda binaria manualmente aplicando la clave dentro del bucle. Este patrón aparece al buscar en una lista de objetos mediante uno de sus atributos.

El error más común es olvidar validar el resultado después de llamar a bisect_left. La función siempre devuelve un índice de inserción válido, pero no garantiza que el elemento de ese índice sea igual al objetivo. Compruebe siempre arr[result] == target antes de dar por hecho que se encontró el objetivo.

Un segundo error consiste en usar bisect_right cuando se quiere obtener la primera ocurrencia: bisect_right devuelve la posición posterior a la última ocurrencia, por lo que restar 1 proporciona la última, no la primera.

Use bisect_left cuando necesite: la primera ocurrencia del objetivo, el punto de inserción que desplaza las ocurrencias existentes hacia la derecha o comprobar si existe el objetivo. Use bisect_right cuando necesite: la posición posterior a la última ocurrencia, el punto de inserción después de todas las ocurrencias existentes o el recuento de elementos <= target (es igual a bisect_right(arr, target)).

Ambas se ejecutan en O(log n) y forman parte de la biblioteca estándar de Python, por lo que puede importarlas y usarlas directamente, a menos que el entrevistador le pida implementarlas desde cero.

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección ha aprendido que: bisect_left encuentra el primer elemento >= target, bisect_right encuentra el primer elemento > target (la posición posterior a la última ocurrencia) y su diferencia proporciona el recuento de apariciones en O(log n). A continuación, exploraremos la búsqueda binaria en el espacio de respuestas, donde el espacio de búsqueda es un rango de posibles respuestas, no un índice de array.