Búsqueda en Arrays Rotados: Encontrar Entero en Lista Ordenada

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

Resumen

¿Qué es el problema "Search in Rotated Arrays"?

El problema "Search in Rotated Arrays" es un reto común en las entrevistas técnicas y desafíos de programación. Se trata de trabajar con una lista de enteros que está ordenada de manera ascendente, pero que ha sido rotada en un índice desconocido. Esta rotación da como resultado una lista en la que los números parece que están desordenados, aunque en realidad mantiene un patrón de orden. El objetivo del problema es encontrar un número dentro de esta lista rotada y, si no lo encontramos, debemos retornar -1.

¿Cómo se estructura el array rotado?

Cuando hablamos de un array rotado, nos referimos a una lista que originalmente está ordenada y que se ha modificado rotando sus elementos desde un punto de pivote. Por ejemplo, si tenemos la lista original [0, 1, 2, 4, 5, 6, 7], y esta rotara en el pivote 3, el resultado sería [4, 5, 6, 7, 0, 1, 2]. Este tipo de rotación conserva el orden relativo de los elementos dentro de sus nuevos segmentos.

Lista Original: [0, 1, 2, 4, 5, 6, 7]
Lista Rotada: [4, 5, 6, 7, 0, 1, 2]

¿Cómo resolver el problema utilizando búsqueda binaria?

Aunque la lista rotada no parece estar ordenada a simple vista, se puede aplicar la técnica de búsqueda binaria debido a su estructura rotada. La búsqueda binaria es un algoritmo eficiente que se utiliza generalmente en listas ordenadas, lo que nos permite encontrar el índice de un elemento en un tiempo O(log n). Aquí se aprovecha el hecho de que una parte de la lista siempre estará ordenada.

Procedimiento de búsqueda binaria para arrays rotados

Identificación del segmento ordenado:
- Comparamos los elementos ubicados al inicio y al final de la lista para determinar cuál segmento está ordenado de manera ascendente.
Determinación del pivote:
- Utilizamos los índices medios para revisar si estamos en el segmento ordenado o en el segmento desordenado.
Comparación del objetivo:
- Buscamos el objetivo comparando en qué parte de la lista rotada se encuentra, revisando si está dentro de los límites del segmento ordenado.
Encuentra o retorna -1:
- Si el objetivo se encuentra en el segmento ordenado, ajustamos los índices para seguir buscando en ese segmento. Si no aparece en ninguno de los pasos, retornamos -1.

Ejemplo práctico

Dada la lista rotada [4, 5, 6, 7, 0, 1, 2], queremos buscar el número 0.
- Al aplicar búsqueda binaria y reconocer el segmento ordenado, rápidamente encontramos que el 0 está en la posición 4.

¿Qué hacer si el elemento no está en la lista?

Si tras aplicar el algoritmo de búsqueda binaria no encontramos el elemento que buscamos, la implementación debe retornar -1 para indicar que el elemento objetivo no se encuentra dentro del array rotado.

Este tipo de ejercicio es fundamental para quienes buscan practicar técnicas avanzadas de búsqueda y manipulación de datos en listas y arrays. ¡Así que anímate a intentarlo y a perfeccionar tus habilidades de programación!

Miguel Angel Reyes Moreno

student•

Propongo solución en Python:

from typing import List





def search\_in\_rotated\_array(nums: List\[int], target: int) -> int:

&#x20;   if len(nums) == 1:

&#x20;       return 0 if nums\[0] == target else -1



&#x20;   left = 0

&#x20;   right = len(nums) - 1



&#x20;   while left <= right:

&#x20;       middle = (left + right) // 2

&#x20;       if nums\[middle] == target:

&#x20;           return middle



&#x20;       if nums\[left] <= nums\[middle]:  # \* left half is sorted

&#x20;           if nums\[left] <= target < nums\[middle]:

&#x20;               right = middle - 1

&#x20;           else:

&#x20;               left = middle + 1

&#x20;       else:  # \* right half is sorted

&#x20;           if nums\[middle] < target <= nums\[right]:

&#x20;               left = middle + 1

&#x20;           else:

&#x20;               right = middle - 1



&#x20;   return -1

Juan Pablo Reina Gutierrez

student•

Esta es mi solución en Java:

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 void main(String[] args) {
        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 + ", num buscado: " + numBuscado);

        target = 3;
        numBuscado = buscarEnArregloRotado(numsRot, k, target);
        System.out.println("Target: " + target + ", num buscado: " + numBuscado);
    }
}

Nicolas Alpargatero

student•

En lo personal le agregaría una variante, me imagino que ya existe, que sería busque la mitad y vecinos. Con esto no estoy buscando solo 1 valor sino 3 cada vez que divido. . Big O notation sigue siendo O(log n)

Said Josue Calixtro Maldonado

student•

Hola, esta es la solución a la que llegué.

Comenzaríamos con dos apuntadores a los extremos.
- i: Apuntador izquierdo, comienza en 0.
- d: Apuntador derecho, comienza en len(s) - 1.
Calculamos la posición del punto medio m = (i + d) // 2.

Antes de pasar al siguiente paso, podemos ver que m divide al array en dos partes diferentes o rangos. Utilizando los dos apuntadores extremos podemos conocer algo importante: cuál de las dos partes está ordenada. Para esto tendríamos dos casos:

nums[m] < nums[d]: El arreglo esá ordenado en el rango de números desde m hasta d, pero no podemos asegurar nada con los números restantes.
nums[m] > nums[i]: El arreglo está ordenado en el rango de números desde i hasta m, pero no podemos asegurar nada con los restantes.

Una vez que conocemos qué rango está ordenado, podemos preguntarnos: ¿el número que busco está dentro del rango ordenado? Si la respuesta es afirmativa entonces continuamos la búsqueda en ese rango de valores, si no, es probable que el número que buscamos esté en el otro rango, el cual no conocemos a partir de qué valor está ordenado.

Antes de mover los apuntadores, podemos revisar si el valor que buscamos está en i, m o d. Si no, entonces actualizamos alguno de los apuntadores extremos.
Para actualizar alguno de los apuntadores extremos (i o d) se siguen las siguientes condiciones:
- target está en el rango ordenado:
  - Si el rango ordenado era [m, d] entonces movemos a i usando i = m + 1.
  - Si el rango ordenado era [i, m] entonces movemos a d usando d = m - 1.
- target no está en el rango ordenado:
  - Si el rango ordenado era [m, d], entonces movemos a d usando d = m - 1.
  - Si el rango ordenado era [i, m], entonces movemos a i usando i = m + 1.

Esto lo repetimos hasta encontrar al número que buscamos o hasta que los dos apuntadores estén juntos.

En resumen, sería buscar qué rango de valores está ordenado y si nuestro número está en ese rango, continuaríamos como una búsqueda binaria normal. En caso de que no esté en el rango ordenado, entonces buscaríamos en el rango faltante, volviendo a verificar el orden de los números y si el valor que buscamos se encuentra en ese rango.