¿Cómo encontrar un elemento en arrays rotados?
Buscar un elemento en un array rotado puede parecer un desafío, pero no es insuperable. En este artículo, exploraremos una técnica de búsqueda eficiente que puede aplicarse a este problema: el uso de la búsqueda binaria con algunas adaptaciones. Analizaremos cómo implementarla en C++ y qué aspectos debemos considerar para asegurar que funcione correctamente incluso en arrays rotados.
¿Cuál es el primer paso para implementar la búsqueda en un array rotado?
Primero, es fundamental entender cómo funciona un array rotado. En esencia, es un array ordenado que ha sido girado en un punto desconocido. Comenzaremos configurando dos apuntadores: uno al inicio (izquierda) y otro al final (derecha) del array. Establecemos izquierda en 0 y derecha en el índice final del array menos uno, ya que este algoritmo utiliza un enfoque de búsqueda binaria optimizado para arrays rotados.
¿Cómo definimos la "mitad" en la búsqueda binaria?
La búsqueda binaria requiere obtener el punto medio entre izquierda y derecha, que se calcula usando la fórmula:
int mitad = izquierda + (derecha - izquierda) / 2;
Esta expresión evita desbordamientos potenciales y representa con precisión la mitad del intervalo. Continuaremos dividiendo el espacio de búsqueda hasta encontrar el valor objetivo o concluir que no está presente.
¿Qué casos debemos considerar al implementar la búsqueda?
En el contexto de arrays rotados, hay cuatro situaciones posibles a evaluar:
mitad es igual al objetivo, retornamos mitad como la posición encontrada.izquierda y derecha según la situación actual.¿Cómo se trata un espacio rotado en la búsqueda binaria?
Para cumplir con las necesidades de un array rotado, debemos ajustar el método tradicional de búsqueda binaria. Cuando el array se identifica como rotado, consideramos las posiciones de los extremos (izquierda y derecha) para determinar en qué segmento debemos buscaren la siguiente iteración. Aquí está un ejemplo de cómo codificar estos ajustes:
if (numeros[izquierda] <= numeros[mitad]) { if (objetivo >= numeros[izquierda] && objetivo < numeros[mitad]) { derecha = mitad - 1; } else { izquierda = mitad + 1; } } else { if (objetivo > numeros[mitad] && objetivo <= numeros[derecha]) { izquierda = mitad + 1; } else { derecha = mitad - 1; } }
¿Cómo evaluamos la efectividad del código?
La complejidad temporal es O(log N), lo que lo hace eficiente para grandes cantidades de datos al reducir significativamente el número de comparaciones requeridas. La complejidad espacial es O(1), que indica que el algoritmo utiliza un espacio constante. Ahora, es tu turno de poner a prueba este algoritmo en diferentes escenarios y dar retroalimentación sobre el proceso. Comparte tus soluciones y resultados para enriquecer la experiencia de aprendizaje de todos.
Recuerda, la programación es un viaje de constante aprendizaje y colaboración. ¡Sigue explorando y compartiendo tus conocimientos!
Buscar un elemento en un array rotado puede parecer un desafío, pero no es insuperable. En este artículo, exploraremos una técnica de búsqueda eficiente que puede aplicarse a este problema: el uso de la búsqueda binaria con algunas adaptaciones. Analizaremos cómo implementarla en C++ y qué aspectos debemos considerar para asegurar que funcione correctamente incluso en arrays rotados.
Primero, es fundamental entender cómo funciona un array rotado. En esencia, es un array ordenado que ha sido girado en un punto desconocido. Comenzaremos configurando dos apuntadores: uno al inicio (izquierda) y otro al final (derecha) del array. Establecemos izquierda en 0 y derecha en el índice final del array menos uno, ya que este algoritmo utiliza un enfoque de búsqueda binaria optimizado para arrays rotados.
La búsqueda binaria requiere obtener el punto medio entre izquierda y derecha, que se calcula usando la fórmula:
int mitad = izquierda + (derecha - izquierda) / 2;
Esta expresión evita desbordamientos potenciales y representa con precisión la mitad del intervalo. Continuaremos dividiendo el espacio de búsqueda hasta encontrar el valor objetivo o concluir que no está presente.
En el contexto de arrays rotados, hay cuatro situaciones posibles a evaluar:
mitad es igual al objetivo, retornamos mitad como la posición encontrada.izquierda y derecha según la situación actual.Para cumplir con las necesidades de un array rotado, debemos ajustar el método tradicional de búsqueda binaria. Cuando el array se identifica como rotado, consideramos las posiciones de los extremos (izquierda y derecha) para determinar en qué segmento debemos buscaren la siguiente iteración. Aquí está un ejemplo de cómo codificar estos ajustes:
if (numeros[izquierda] <= numeros[mitad]) {
if (objetivo >= numeros[izquierda] && objetivo < numeros[mitad]) {
derecha = mitad - 1;
} else {
izquierda = mitad + 1;
}
} else {
if (objetivo > numeros[mitad] && objetivo <= numeros[derecha]) {
izquierda = mitad + 1;
} else {
derecha = mitad - 1;
}
}
La complejidad temporal es O(log N), lo que lo hace eficiente para grandes cantidades de datos al reducir significativamente el número de comparaciones requeridas. La complejidad espacial es O(1), que indica que el algoritmo utiliza un espacio constante. Ahora, es tu turno de poner a prueba este algoritmo en diferentes escenarios y dar retroalimentación sobre el proceso. Comparte tus soluciones y resultados para enriquecer la experiencia de aprendizaje de todos.
Recuerda, la programación es un viaje de constante aprendizaje y colaboración. ¡Sigue explorando y compartiendo tus conocimientos!
Hay un error que stá en la parte para buscar en la mitad derecha, ya que hay que comprobar que el objetivo sea mayor que el número de la mitad:
else:
if objetivo <= nums[derecha] and objetivo > nums[mitad]:
izquierda = mitad + 1
else:
derecha = mitad - 1
Por si necesitas entender lo que pasó, trataré de explicarlo:
.
(1) Daré por hecho que entendiste hasta la condición nums[mitad] == objetivo.
.
(2) Después deberás identificar si una mitad está ordenada o rotada. Una mitad está ordenada si la posición mitad es menor o igual que la posición derecha (nums[mitad] <= nums[derecha]), o lo contrario (nums[izq] <= nums[mitad]).
#L M R
[4,5,6,1,2,3,4] # mitad = 3
[1,2,3,4] #Ordenada
[4,5,6,1] #Rotada
.
(3) Si lo evaluado está ordenado desde la mitad a la derecha, entonces debemos identificar si el objetivo está dentro del intervalo [mitad,derecha], es decir, (nums[mitad] <= obj && nums[derecha] >= obj), si está dentro, entonces cambiamos el valor de izquierda por mitad + 1, si no se cumple, entonces cambiamos el valor de derecha por mitad - 1. También se puede evaluar si el objetivo está fuera del intervalo ordenado, pero es algo que te lo dejo de tarea.
.
(4) Si lo evaluado no está ordenado desde la mitad a la derecha, quiere decir que está . Por lo tanto, realizamos lo mismo que el anterior paso, teniendo en cuenta que lo demás está , desde la . Entonces evaluamos si el está en el intervalo , es decir, (), si lo está , caso contrario .
.
En conclusión, debes identificar si los elementos desde la mitad a la derecha están ordenados o rotados, después evaluar si el objetivo está en el intervalo ordenado o rotado y según eso mover los apuntadores y según corresponde. Es por eso que el código tiene dos anidados dentro de un .
.
Comparto la solución cuando se evalúa que el objetivo esté en el intervalo rotado.
objetivo[izq,mitad]nums[izq] <= obj && nums[mitad] >= objderecha = mitad -1izq = mitad +1izquierdaderechaifif/elseNo se si la profe por equivocacion en el condicional while se confundio y en lugar de poner nums como variable dentro del if coloco numeros, por si se deja con numeros como variable el algoritmo falla
Hay que ir escribiendo test unitarios para probar y tambien para practicar
la condición de nums[mitad]>=nums[izquierda] puede causar un error, ejemplo en este caso : [4,5,5,6,0,1,2,3] izquierda = 1 mitad = 2 debería de ser solo mayor
Comparto mi solución en JS
export function searchInRotatedArray(nums, objetivo) {
let left = 0;
let right = nums.length - 1;
let middle;
while (left <= right) {
middle = left + Math.floor((right - left) / 2);
if (nums[middle] === objetivo)
return middle;
if (nums[middle] < nums[right]) {
if (objetivo > nums[middle]) {
left = middle + 1;
}
else {
right = middle - 1;
}
}
else {
//Rotated
if (objetivo > nums[middle]) {
right = middle - 1;
}
else {
left = middle + 1;
}
}
}
return -1;
}
👨💻 Solución alternativa
Basada en la función que ya tenemos de búsqueda binaría:
function binarySeary() {...}
export function searchInRotatedArray(nums, target) {
// Esto significa que nums está totalmente ordenado
if (nums[0] < nums.at(-1)) {
return binarySeary(nums, target)
}
let indexOfRotation = -1
// Encontramos en qué índice se rotó el array
// [3,4,5,0,1,2]
// ^ <-- indexOfRotation = 3
for (let i=0; i<nums.length; i++) {
if (nums[i] > nums[i+1]) {
indexOfRotation = i+1
break
}
}
// La condición nos dice que el target está en el segundo array
// arr=[3,4,5,0,1,2], target=1
// Entonces buscamos en [0,1,2]
if (target >= nums[indexOfRotation] && target < nums[0]) {
const found = binarySeary(nums.slice(indexOfRotation), target)
// Si existe sumamos para obtener el índice en el array original
return found === -1 ? -1 : indexOfRotation + found
}
// Si llegamos aquí el target está en la primera mitad
return binarySeary(nums.slice(0, indexOfRotation), target)
}
Finnaly My First Favorite ProgrAmming Languages, I liked Cpp . I am Cpp DevBoy. \n
//Search in Routated Array nums[ target ] if not in nums return -1 ....
#include<iostream>
#include<vector>
using namespace std ;
int p = 0;
int SearchInRotatedArray ( vector<int> &nums, int target ) ;
int main ( void ) {
vector<int> Arr = { 1,3,5,7,9,2,4,6,8 } ;
int trgt = 5 ;
p = SearchInRotatedArray( Arr, trgt ) ;
if ( p == -1 )
cout << " Target was Never Found in Array "<< "\n" ;
else
cout <<" Target was Found at Position:\t"<< p <<" in Array Nums" << "\n";
// cout << endl;
return 0 ;
}
int SearchInRotatedArray ( vector<int> &nums, int target ) {
int left = 0;
int right = nums.size() -1 ;
int mid = 0;
while ( left <= right ) {
mid = ( left + right ) / 2 ;
if ( nums[ mid ] == target )
return mid ;
if ( nums[ mid ] > nums[ left] ) {
// If target is within the left half range
if ( target >= nums[ left ] && target < nums[ mid ] )
right = mid -1 ;
else
left = mid + 1 ;
}
else {
// If target is within the right half range
if ( target <= nums[ right ] && target < nums[ mid ] )
left = mid + 1 ;
else
right = mid - 1 ;
}
}
return -1 ; // Target was not found
}
En Python
def search_in_rotated_sorted_array(nums, target):
"""
Busca un elemento en un arreglo rotado y ordenado.
Args:
nums: El arreglo rotado.
target: El elemento a buscar.
Returns:
El índice del elemento si se encuentra, -1 en caso contrario.
"""
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# Determinar si la mitad izquierda está ordenada
if nums[left] <= nums[mid]:
# Si el objetivo está en la mitad izquierda
if target >= nums[left] and target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
# Si el objetivo está en la mitad derecha
if target > nums[mid] and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1