Este problema consiste en localizra las posiciones de inicio y fin de un valor objetivo específico dentro de un arreglo de enteros ordenado. La restricción principal es que la complejidad del algoritmo debe ser de orden O(log n).
Si el valor objetivo no se encuentra en el arreglo, la función debe devolver [-1, -1].
Por ejemplo, dado el arreglo [5, 7, 7, 8, 8, 10] y el valor objetivo 8, el resultado esperado es [3, 4].
Solución con Búsqueda Binaria Modificada Una estrategia eficiente para resolver este problema con la complejidad requerida es adaptar el algoritmo de búsqueda binaria. Podemos emplear dos funciones de búsqueda binaria personalizadas:
- Una función para encontrar el índice más a la izquierda (el inicio del rango) de un elemento mayor o igual al objetivo.
- Otra función para encontrar el índice más a la derecha (el fin del rango) de un elemento menor o igual al objetivo. Combinando los resultados de estas dos búsquedas, podemos determinar el rango del valor objetivo.
Código de Ejemplo (C++)
#include <vector>
#include <algorithm>
class Solution {
private:
// Encuentra el índice del primer elemento >= target
int findFirstGreaterOrEqual(const std::vector<int>& nums, int target) {
int low = 0;
int high = nums.size(); // Usamos nums.size() como límite superior exclusivo
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] < target) {
low = mid + 1;
} else {
high = mid; // nums[mid] podría ser el primero, así que mantenemos 'mid'
}
}
return low; // 'low' será el índice del primer elemento >= target, o nums.size() si todos son < target
}
// Encuentra el índice del primer elemento > target
int findFirstGreater(const std::vector<int>& nums, int target) {
int low = 0;
int high = nums.size(); // Usamos nums.size() como límite superior exclusivo
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] <= target) { // Buscamos el primer elemento estrictamente mayor
low = mid + 1;
} else {
high = mid; // nums[mid] podría ser el primero mayor, así que mantenemos 'mid'
}
}
return low; // 'low' será el índice del primer elemento > target, o nums.size() si todos son <= target
}
public:
std::vector<int> searchRange(std::vector<int>& nums, int target) {
if (nums.empty()) {
return {-1, -1};
}
int start_index = findFirstGreaterOrEqual(nums, target);
int end_index_plus_one = findFirstGreater(nums, target);
// Verificamos si el target se encontró y si el rango es válido
if (start_index < nums.size() && nums[start_index] == target) {
// El índice final es el elemento anterior al primer elemento > target
return {start_index, end_index_plus_one - 1};
} else {
return {-1, -1};
}
}
};
Solución Alternativa: Búsqueda Inicial y Expansión Otra aproximación consiste en realizar una búsqueda binaria estándar para encontrar cualquier ocurrencia del valor objetivo. Una vez encontrada una instancia, se expande la búsqueda hacia la izquierda y hacia la derecha para determinar los límites exactos del rango.
Código de Ejemplo (C++)
#include <vector>
class Solution {
public:
std::vector<int> searchRange(std::vector<int>& nums, int target) {
int n = nums.size();
if (n == 0) {
return {-1, -1};
}
int low = 0, high = n - 1;
int found_index = -1;
// Búsqueda binaria para encontrar una ocurrencia del target
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
found_index = mid;
break; // Encontramos una instancia
} else if (nums[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
if (found_index == -1) {
return {-1, -1}; // Target no encontrado
}
// Expandir hacia la izquierda para encontrar el inicio del rango
int start = found_index;
while (start > 0 && nums[start - 1] == target) {
start--;
}
// Expandir hacia la derecha para encontrar el fin del rango
int end = found_index;
while (end < n - 1 && nums[end + 1] == target) {
end++;
}
return {start, end};
}
};
Solución Concisa con Iteradores (C++) Se puede lograr una solución más compacta utilizando las funciones de la biblioteca estándar de C++, como std::find y std::find_if con iteradores inversos.
Código de Ejemplo (C++)
#include <vector>
#include <algorithm>
#include <iterator> // Para std::distance
class Solution {
public:
std::vector<int> searchRange(std::vector<int>& nums, int target) {
auto it_start = std::find(nums.begin(), nums.end(), target);
if (it_start == nums.end()) {
return {-1, -1}; // Target no encontrado
}
// Para encontrar el final, buscamos el target desde el final del vector
auto it_end_rev = std::find(nums.rbegin(), nums.rend(), target);
// Convertir iterador inverso a iterador normal y calcular la distancia
// it_end_rev.base() apunta al elemento *después* del target en la dirección normal
// Por lo tanto, necesitamos restar 1 para obtener el índice del último target
int start_pos = std::distance(nums.begin(), it_start);
int end_pos = std::distance(nums.begin(), it_end_rev.base()) - 1;
return {start_pos, end_pos};
}
};
Solución en Python Una implementación en Python puede aprovechar métodos integrados para una solución legible, aunque la eficiencia de in y index puede variar y no siempre garantiza O(log n) por sí solos si no se implementan internamente con búsqueda binaria para listas ordenadas.
Código de Ejemplo (Python)
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
result = [-1, -1]
n = len(nums)
# Búsqueda binaria para encontrar el primer índice >= target
low, high = 0, n
while low < high:
mid = low + (high - low) // 2
if nums[mid] < target:
low = mid + 1
else:
high = mid
start_index = low
# Verificar si encontramos el target
if start_index == n or nums[start_index] != target:
return result
result[0] = start_index
# Búsqueda binaria para encontrar el primer índice > target
low, high = start_index, n # Empezamos la búsqueda desde start_index
while low < high:
mid = low + (high - low) // 2
if nums[mid] <= target: # Buscamos el primer elemento estrictamente mayor
low = mid + 1
else:
high = mid
# El índice final es el elemento anterior al primer elemento > target
result[1] = low - 1
return result