Búsqueda en Arrays Rotados con C++

Clase 30 de 35 • Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Resumen

¿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:

Valor encontrado: Si el elemento en la posición mitad es igual al objetivo, retornamos mitad como la posición encontrada.
Espacio ordenado: Si la parte izquierda o derecha del array está ordenada, procedemos con una búsqueda binaria regular en esa sección.
Espacio desordenado: Si el array parece desordenado, evaluamos si el objetivo podría estar antes o después del punto medio, tomando decisiones de movimiento opuestas.
Caso por omisión: Si después de evaluar las condiciones anteriores, no hay una conclusión, ajustamos los apuntadores 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!

Juan Pablo Reina Gutierrez

student•

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

Carlos Hernandez

student•

Gracias por tu aporte! En efecto había un error y con eso queda solucionado

Christopher Andrés Guano Valencia

student•

👨‍💻Explicación del Algoritmo

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á ROTADO. Por lo tanto, realizamos lo mismo que el anterior paso, teniendo en cuenta que lo demás está ORDENADO, desde la izquierda a la mitad. Entonces evaluamos si el objetivo está en el intervalo [izq,mitad], es decir, (nums[izq] <= obj && nums[mitad] >= obj), si lo está derecha = mitad -1, caso contrario izq = mitad +1. . 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 izquierda y derecha según corresponde. Es por eso que el código tiene dos if anidados dentro de un if/else. . Comparto la solución cuando se evalúa que el objetivo esté en el intervalo rotado.

Ivan Camilo Buitrago Buitrago

student•

No 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

Reinaldo Mendoza

student•

Hay que ir escribiendo test unitarios para probar y tambien para practicar

Carlos Raúl Romero Martínez

student•

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

Nicolas Alpargatero

student•

Probe el código de la profe con tus parámetros y me dio correctamente.

Diego Herrera Prado

student•

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;
}

José Emanuel Osorio Vázquez

student•

👨‍💻 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)
}

Bryan Castano

student•

Finnaly My First Favorite ProgrAmming Languages, I liked Cpp . I am Cpp DevBoy. \n

Bryan Castano

student•

//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
    
}

Jovanny Delgado

student•

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

Miguel Angel Reyes Moreno

student•

Este código tiene errores y eso pasa por copiar y pegar. La solución correcta es:

\#include \<vector>int searchInRotatedArray(vector\<int> \&nums, int target) {  int izquierda = 0;  int derecha = nums.size() - 1;  int mitad;
&#x20; while (izquierda <= derecha) {    mitad = izquierda + (derecha - izquierda) / 2;    if (nums\[mitad] == target) {      return mitad;    }    if (nums\[mitad] >= nums\[izquierda]) {      if (target >= nums\[izquierda] && target < nums\[mitad]) {        derecha = mitad - 1;      } else {        izquierda = mitad + 1;      }    } else {      if (target > nums\[mitad] && target <= nums\[derecha]) {        izquierda = mitad + 1;      } else {        derecha = mitad - 1;      }    }  }
&#x20; return -1;}

Héctor Hugo Cuzco Alvarez

student•

En Go:

Héctor Hugo Cuzco Alvarez

student•

En Go:

Héctor Hugo Cuzco Alvarez

student•

En Golang:

func searchInRotatedArray(nums []int, objetivo int) int {
	l, r := 0, len(nums) - 1
	for l <= r {
		m := l + (r-l)/2
		if objetivo == nums[m] {
			return m
		}
		if objetivo > nums[m] && objetivo <= nums[r] {
			l = m + 1
		} else if objetivo < nums[m] && objetivo >= nums[l] {
			r = m - 1
		} else if objetivo <= nums[r] {
			l = m + 1
		} else {
			r = m - 1
		}
	}
	return -1
} 
```&#x20;

Victor Hugo Vázquez Gómez

student•

En el if que esta dentro del primer else esta mal, tiene que ser:

objetivo <= numeros[derecha] && objetivo > numeros[mitad]

ademas de que es nums, no numeros.

Joan paredes yupanqui

student•

Misael Mondragón Lenis

student•

Solución en js

export function searchInRotatedArray(nums, objetivo) {
  let i = 0;
  let d = nums.length - 1;
  let p;
  while (i < d) {
    p = Math.floor(i + (d - i) / 2);
    if (nums[p] == objetivo) {
      return p
    }
    if (nums[d] == objetivo) {
      return d
    }
    if (nums[i] == objetivo) {
      return i
    }
    // mirar si estoy parado antes del pivote
    if (nums[p] > nums[i]) {
      // objective between i and p
      if (nums[p] >= objetivo && nums[i] <= objetivo) {
        // descartar der
        d = p;
      } else {
        // descartar izq
        i = p;
      }
    } else {
      // objective between p and d
      if (nums[p] <= objetivo && nums[d] >= objetivo) {
        // descartar izq
        i = p;
      } else {
        // descarto izq
        d = p;
      }
    }
  }
  return -1
}

Juan Pablo Reina Gutierrez

student•

Esta es mi solución definitiva:

public class SearchInRotatedArrays {

    public static int busquedaBinaria(int[] nums, int izquierda, int derecha, int target) {
        int mitad;
        while (izquierda <= derecha) {
            mitad = izquierda + (derecha - izquierda) / 2;

            if (nums[mitad] == target) {
                return mitad;
            } else if (nums[mitad] < target) {
                izquierda = mitad + 1;
            } else {
                derecha = mitad - 1;
            }
        }
        return -1;
    }

    public static int[] rotarArreglo(int[] nums, int k) {
        int[] numsRot = new int[nums.length];
        for (int i = k, j = 0; i < nums.length; i++, j++) {
            numsRot[j] = nums[i];
        }

        for (int i = 0, j = k + 1; i < k; i++, j++) {
            numsRot[j] = nums[i];
        }

        return numsRot;
    }

    public static int buscarEnArregloRotado(int[] nums, int k, int target) {
        int izquierda = 0;
        int derecha = k;

        if (nums[izquierda] == target) {
            return izquierda;
        }

        if (nums[derecha] == target) {
            return derecha;
        }

        if (target <= nums[derecha] && target >= nums[izquierda]) {
            return busquedaBinaria(nums, izquierda, derecha, target);
        }

        izquierda = k + 1;
        derecha = nums.length - 1;

        if (nums[izquierda] == target) {
            return izquierda;
        }

        if (nums[derecha] == target) {
            return derecha;
        }

        if (target <= nums[derecha] && target >= nums[izquierda]) {
            return busquedaBinaria(nums, izquierda, derecha, target);
        }

        return -1;
    }

    public static int buscarEnArregloRotado(int[] nums, int target) {
        int mitad;
        int izquierda = 0;
        int derecha = nums.length - 1;

        while (izquierda <= derecha) {
            mitad = izquierda + (derecha - izquierda) / 2;

            if (nums[mitad] == target) {
                return mitad;
            } else if (nums[izquierda] > nums[derecha] && nums[mitad] < target) {
                izquierda = mitad + 1;
            } else if (nums[izquierda] > nums[derecha] && nums[mitad] > target) {
                izquierda = mitad + 1;
            } else if (nums[mitad] < target) {
                izquierda = mitad + 1;
            } else {
                derecha = mitad - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println("Versión 1:");
        int[] nums = {0, 1, 2, 4, 5, 6, 7};
        int k = 3;

        int[] numsRot = rotarArreglo(nums, k);
        System.out.println(Arrays.toString(numsRot));

        int target = 0;

        int numBuscado = buscarEnArregloRotado(numsRot, k, target);
        System.out.println("Target: " + target + ", indice encontrado: " + numBuscado);

        target = 3;
        numBuscado = buscarEnArregloRotado(numsRot, k, target);
        System.out.println("Target: " + target + ", indice encontrado: " + numBuscado);

        System.out.println();
        System.out.println("Versión 2:");

        nums = new int[]{4, 5, 6, 7, 0, 1, 2};
        target = 0;
        System.out.println(Arrays.toString(nums));
        numBuscado = buscarEnArregloRotado(nums, target);
        System.out.println("Target: " + target + ", indice encontrado: " + numBuscado);
        target = 3;
        numBuscado = buscarEnArregloRotado(nums, target);
        System.out.println("Target: " + target + ", indice encontrado: " + numBuscado);

        nums = new int[]{12, 13, 9, 10, 11};
        target = 10;
        System.out.println(Arrays.toString(nums));
        numBuscado = buscarEnArregloRotado(nums, target);
        System.out.println("Target: " + target + ", indice encontrado: " + numBuscado);
    }
}

Nicolas Alpargatero

student•

Comparto el código de la profe en Python

Emilio Sala

student•

en python

def searh_rotated_array(nums, target):
   left = 0
   right = len(nums) - 1
   while (left <= right): 
      mid = (left + right) // 2
      if (nums[mid] == target):
         return mid
      if nums[left] > target:
         left = mid + 1
         continue
      elif (nums[right] > target):
         right = mid - 1
         continue
      if( nums[mid] < target and target <= nums[right]):
         left = mid + 1
      else:
         right = mid - 1
   return -1

print(searh_rotated_array( [4, 5, 6, 7, 0, 1, 2],4))
print(searh_rotated_array( [4, 5, 6, 7, 0, 1, 2],6))
print(searh_rotated_array( [4, 5, 6, 7, 0, 1, 2],2))
print(searh_rotated_array( [4, 5, 6, 7, 0, 1, 2],0))