Entrevista técnica de código: Encontrar la primera y última posición con búsqueda binaria

Problema y contexto de aplicación

Dado un arreglo de enteros nums ordenado en orden no decreciente y un entero target, devuelve el primer y último índice de target. Devuelve [-1, -1] cuando esté ausente. El arreglo puede estar vacío y contener duplicados, y la función no debe mutarlo. La complejidad temporal requerida es O(log n) con un espacio adicional de O(1).

Por ejemplo, nums = [1, 2, 2, 2, 3] y target = 2 devuelve [1, 3]; target = 4 devuelve [-1, -1]. Un escaneo lineal puede generar la respuesta, pero su peor caso de O(n) infringe el requisito.

Esta pregunta es habitual en rondas de código para puestos de ingeniería de software y algoritmos. La guía de entrevistas actual de SDE II de Amazon espera código sintácticamente correcto, escalable, robusto y bien probado, y LeetCode mantiene el mismo problema central. La verdadera prueba no es memorizar dos plantillas. Consiste en definir el límite de búsqueda con la suficiente precisión para que la condición del bucle, las actualizaciones de intervalos y el valor de retorno sigan un mismo invariante.

Qué evalúa el entrevistador

La primera señal es si el candidato reconoce que encontrar cualquier aparición es insuficiente. Una búsqueda binaria ordinaria que retorna al encontrar una igualdad no garantiza la aparición más a la izquierda ni más a la derecha. Encontrar una aparición y luego escanear hacia afuera sigue degradándose a O(n) cuando cada elemento es igual al objetivo.

La segunda señal es la semántica de los límites. Una descomposición limpia busca dos puntos de inserción:

• lowerBound: la primera posición cuyo valor sea mayor o igual que target.
• upperBound: la primera posición cuyo valor sea estrictamente mayor que target.

Las funciones oficiales de Python bisect_left y bisect_right utilizan estas definiciones de partición. Una vez que ambos puntos son correctos, un objetivo existente ocupa [lowerBound, upperBound - 1].

La tercera señal es el invariante del bucle. Con un intervalo semiabierto [left, right), un arreglo vacío comienza naturalmente como [0, 0), y la terminación es left === right. Mezclar una regla de intervalo cerrado con una inicialización semiabierta, como establecer right en nums.length y leer después nums[right], genera un acceso fuera de límites o un bucle infinito.

Por último, el entrevistador busca la verificación. Una respuesta sólida cubre un arreglo vacío, un solo elemento, todos duplicados, un objetivo por debajo del mínimo, un objetivo por encima del máximo, objetivos en ambos extremos y un objetivo ausente. También explica por qué target + 1 no es una técnica general de límite superior: depende de un sucesor numérico discreto, crea un valor fuera de dominio en el entero seguro más grande y no se extiende a cadenas ni a comparadores personalizados.

Preguntas de aclaración antes de responder

• ¿El arreglo ya está ordenado? Este enunciado garantiza un orden no decreciente. Ordenar una entrada no ordenada mientras

se preservan los índices originales cambia el modelo de datos y elimina el límite total de O(log n).

• ¿Devolvemos índices originales u ordenados? Son los mismos aquí porque la entrada ya está ordenada.
• ¿Qué representa la ausencia? Este enunciado requiere [-1, -1]; un punto de inserción no es automáticamente una coincidencia.
• ¿Se permiten valores duplicados? Sí. Los duplicados son la razón por la que se necesitan búsquedas de límites.
• ¿El arreglo puede estar vacío? Sí. Una implementación semiabierta lo maneja sin leer ningún extremo.
• ¿Cuál es el dominio numérico? Los valores son enteros seguros de JavaScript. La solución no calcula target + 1, por lo que

no fabrica un centinela fuera de dominio solo para encontrar un límite.

• ¿Se debe implementar la búsqueda binaria? Sí para este ejercicio de entrevista. En producción, prefiera una función de la biblioteca estándar

cuando su contrato coincida exactamente.

• ¿Se puede mutar la entrada? No, y ninguna de las búsquedas de límites necesita mutarla.

Estructura de respuesta en 30 segundos

“Ejecutaría dos búsquedas de límites en lugar de encontrar una aparición y escanear. lowerBound busca en el intervalo semiabierto [left, right) el primer valor mayor o igual que target; upperBound encuentra el primer valor estrictamente mayor que target. Cada iteración utiliza middle = left + floor((right - left) / 2). Si el punto medio sigue en el lado izquierdo del objetivo, establezco left = middle + 1; de lo contrario, retengo el punto medio con right = middle. Primero verifico si el límite inferior está fuera de rango o no es igual al objetivo. Si existe, la respuesta es [lower, upper - 1]. Dos búsquedas se mantienen en O(log n) con un espacio adicional de O(1)”.

Análisis paso a paso a profundidad

Paso 1: Reescribir “primero y último” como dos puntos de partición.

Para nums = [1, 2, 2, 2, 3] y target = 2:

lowerBound = 1  // first nums[i] >= 2
upperBound = 4  // first nums[i] > 2
answer = [1, 4 - 1] = [1, 3]

Esta definición es más fácil de verificar que “seguir buscando a la izquierda” y “seguir buscando a la derecha”. Los puntos de inserción siguen siendo significativos cuando el objetivo está ausente. Para target = 4, ambos son iguales a la longitud del arreglo 5, pero eso no significa que el objetivo exista. El algoritmo debe comprobar por separado nums[lower] === target.

Paso 2: Fijar el invariante de intervalo semiabierto.

Al inicio de cada iteración de lowerBound:

1. Cada índice por debajo de left contiene un valor estrictamente menor que target.
2. Cada índice en o por encima de right contiene un valor mayor o igual que target.
3. El intervalo de candidatos no resuelto es [left, right).

Inicialmente, left = 0 y right = nums.length; ambas regiones externas están vacías, por lo que el invariante se cumple. Si nums[middle] < target, el punto medio y todo lo que esté a su izquierda no pueden ser la respuesta, por lo que se establece left = middle + 1. De lo contrario, el punto medio podría ser la primera posición válida y debe conservarse, por lo que se establece right = middle.

Cada iteración reduce estrictamente el intervalo. Cuando left === right, no queda ningún elemento sin resolver. Todo en el lado izquierdo es menor y todo en el derecho es mayor o igual que el objetivo, por lo que esta posición es el límite inferior.

upperBound utiliza la misma estructura con una partición diferente:

1. Cada índice por debajo de left contiene un valor menor o igual que target.
2. Cada índice en o por encima de right contiene un valor estrictamente mayor que target.

Por lo tanto, mueve left cuando nums[middle] <= target y, en caso contrario, mueve right.

Paso 3: Implementar ambas funciones de límite.

function lowerBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const middle = left + Math.floor((right - left) / 2);
    if (nums[middle] < target) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }

  return left;
}

function upperBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const middle = left + Math.floor((right - left) / 2);
    if (nums[middle] <= target) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }

  return left;
}

La única diferencia es la comparación. Dos funciones con nombres claros son más fáciles de explicar en una entrevista que una sola función con un selector booleano opaco, y evitan inventar una abstracción genérica compleja para un solo uso.

El punto medio es left + floor((right - left) / 2), por lo que no suma dos índices grandes primero. Los límites de los arreglos en el entorno de ejecución de JavaScript hacen que el desbordamiento de índices sea poco probable en este enunciado, pero la expresión se traslada de forma segura a lenguajes con enteros de ancho fijo.

Paso 4: Combinar los resultados y verificar una coincidencia real.

function searchRange(nums: number[], target: number): [number, number] {
  const first = lowerBound(nums, target);

  if (first === nums.length || nums[first] !== target) {
    return [-1, -1];
  }

  return [first, upperBound(nums, target) - 1];
}

El orden de verificación importa. Pruebe first === nums.length antes de leer nums[first], para que una posición posterior al arreglo no se trate como un elemento. Una vez que se sabe que first coincide, el límite superior es al menos first + 1, y restar uno da la última aparición.

No reemplace el límite superior con lowerBound(nums, target + 1) - 1. Bajo la restricción de enteros seguros de este enunciado, puede que aún devuelva el límite correcto, pero sumar uno a Number.MAX_SAFE_INTEGER abandona el dominio en el que se garantiza la aritmética entera exacta. Si la entrada se expande a Numbers arbitrarios de JavaScript, los enteros adyacentes también pueden colapsar bajo la precisión de punto flotante. Las cadenas, los valores BigInt y los comparadores personalizados no tienen un “siguiente valor” universal. Buscar directamente el primer valor estrictamente mayor que el objetivo expresa el contrato completo.

Paso 5: Demostrar la complejidad.

Cada bucle reduce un intervalo candidato de longitud k a lo sumo a aproximadamente k / 2, por lo que cada función de límite realiza O(log n) comparaciones. Dos búsquedas siguen siendo O(log n). El algoritmo almacena solo un número constante de índices, utiliza O(1) de espacio adicional y no muta el arreglo.

Encontrar cualquier aparición y escanear hacia afuera visita los n elementos para [2, 2, ..., 2], lo que da un peor caso de O(n). Una tabla hash precomputada puede acelerar las búsquedas repetidas, pero su construcción cuesta O(n) de tiempo y espacio. Solo es útil para muchas consultas sobre la misma entrada estática e ignora la ventaja que ofrece el ordenamiento provisto.

Paso 6: Validar con casos límite y pruebas diferenciales aleatorizadas.

Como mínimo, cubra:

Luego, genere arreglos ordenados con duplicados y compare el resultado con la base lineal de indexOf y lastIndexOf. El enfoque lineal no cumple con la complejidad requerida, pero es un excelente oráculo de prueba. Los casos fijos comprueban límites conocidos, mientras que las pruebas diferenciales aleatorizadas exponen errores vinculados a conteos particulares de duplicados o extremos.

Ejemplo de respuesta de alta calidad

“El arreglo ya está ordenado y el requisito es O(log n), por lo que no buscaría un objetivo y escanearía hacia afuera; un arreglo con todos elementos duplicados se volvería lineal. Defino la respuesta con dos puntos de inserción: el primer valor mayor o igual que el objetivo y el primer valor estrictamente mayor que el objetivo.

Ambas búsquedas utilizan el intervalo semiabierto [left, right). Para el límite izquierdo, el invariante establece que todo lo anterior a left es menor que el objetivo y todo desde right en adelante es mayor o igual que este. Si el punto medio es menor, la respuesta debe estar a la derecha, así que establezco left = middle + 1. De lo contrario, el punto medio puede ser la respuesta, por lo que establezco right = middle. Cuando se encuentran, esa posición es el límite inferior. El límite superior solo cambia la condición: los valores menores o iguales al objetivo mueven left.

Calculo el límite inferior primero. Si es igual a la longitud del arreglo o no contiene el objetivo, devuelvo [-1, -1]. De lo contrario, el extremo derecho es el límite superior menos uno. Una entrada vacía, un objetivo ausente, todos duplicados y coincidencias en cualquiera de los extremos utilizan la misma lógica.

Cada iteración divide el intervalo a la mitad, por lo que dos búsquedas siguen siendo O(log n) y utilizan O(1) de espacio adicional. Verificaría casos límite fijos y luego compararía arreglos ordenados aleatorios con indexOf y lastIndexOf. No usaría target + 1, porque inventa un centinela fuera del dominio establecido y no se generaliza a otros dominios ordenados”.

Errores comunes

• Encontrar cualquier aparición y escanear hacia afuera → un arreglo donde todos los elementos son iguales se convierte en O(n) → aplique búsqueda binaria para los límites inferior y superior por separado.
• Retornar inmediatamente ante la igualdad → la coincidencia es arbitraria en lugar de ser la más a la izquierda o más a la derecha → retenga la mitad que aún pueda contener el límite.
• Inicializar right a la longitud y leer nums[right] → el extremo semiabierto no es accesible → lea solo middle y termine cuando ambos extremos se encuentren.
• Actualizar con left = middle → un intervalo de dos elementos podría no reducirse nunca → use middle + 1 al excluir el punto medio.
• Devolver un punto de inserción para un objetivo ausente → una posición de inserción válida no es una coincidencia → verifique los límites y nums[first] !== target.
• Usar target + 1 para el límite derecho → depende de un sucesor inexistente o fuera de dominio → implemente la primera posición estrictamente mayor que el objetivo.
• Mezclar plantillas cerradas y semiabiertas → la inicialización, la condición de bucle y las actualizaciones entran en conflicto → escriba la semántica del intervalo y el invariante antes del código.
• Probar solo duplicados en el centro → la entrada vacía, los extremos y los casos donde no se encuentra el objetivo aún pueden fallar → agregue una tabla de límites y pruebas diferenciales aleatorizadas.
• Afirmar que ordenar y luego buscar sigue siendo O(log n) → la ordenación domina el costo total → aproveche la garantía de entrada ordenada o vuelva a calcular la complejidad completa.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: Si solo necesita comprobar si el objetivo existe, ¿necesita dos búsquedas?

No. Ejecute una búsqueda de límite inferior y verifique que su posición esté dentro del rango y sea igual al objetivo. Eso sigue siendo O(log n). Si una biblioteca estándar proporciona exactamente este contrato, el código de producción puede usarlo directamente. Dos búsquedas son necesarias únicamente para obtener ambos extremos de un rango de duplicados.

Pregunta de seguimiento 2: ¿Cómo devolvería el número de apariciones?

Cuando el objetivo existe, el conteo es upperBound - lowerBound. Cuando está ausente, los dos puntos de inserción son iguales, por lo que la diferencia también es cero. Por lo tanto, una función que solo cuente no necesita siquiera leer un elemento del arreglo. La fórmula funciona porque cada elemento entre los dos límites es igual al objetivo.

Pregunta de seguimiento 3: ¿Qué cambia si el arreglo está ordenado en orden descendente?

Invierta el invariante y las comparaciones. Un límite inferior descendente puede significar el primer valor menor o igual que el objetivo, y el otro límite es el primer valor estrictamente menor que él. No invierta únicamente la interpretación final manteniendo las comparaciones originales. Defina primero el predicado de partición y luego actualice el intervalo a partir de su valor de verdad.

Pregunta de seguimiento 4: ¿Qué sucede si los elementos son objetos y la búsqueda utiliza un solo campo?

Busque en una clave de comparación ordenada, como createdAt. Si la extracción de la clave es costosa a lo largo de consultas repetidas, mantenga un arreglo de claves precalculado; la documentación de Python igualmente recomienda almacenar en caché o precalcular claves costosas. La secuencia de objetos no debe mutarse durante la búsqueda, o el invariante de ordenamiento dejará de cumplirse.

Pregunta de seguimiento 5: ¿Qué sucede si los datos están en una base de datos con un índice ordenado en lugar de estar en memoria?

No traduzca la búsqueda binaria de la aplicación en muchas consultas remotas. Deje que el índice de la base de datos localice el rango, como las claves de ordenación estables mínima y máxima iguales al objetivo o un escaneo de rango por índice. Un viaje de ida y vuelta de red por cada iteración de búsqueda binaria convierte O(log n) comparaciones en llamadas repetidas de alta latencia y puede observar diferentes instantáneas durante escrituras concurrentes.

Pregunta de seguimiento 6: ¿Cómo se extiende esta plantilla a problemas de “respuesta mínima factible”?

Defina un predicado monotónico, como que cada capacidad por debajo de x sea inviable y cada capacidad a partir de cierto punto en adelante sea factible. Luego, aplique el límite inferior al primer predicado verdadero sobre un espacio de respuestas implícito, reemplazando nums[middle] < target con !feasible(middle). Debe demostrarse que el predicado transiciona de falso a verdadero solo una vez; si los valores de verdad alternan, la búsqueda binaria carece de base de corrección.