Search in Rotated Arrays: análisis del problema

Propongo solución en Python: ``` from typing import List def search\_in\_rotated\_array(nums: List\[int], target: int) -> int: if len(nums) == 1: return 0 if nums\[0] == target else -1 left = 0 right = len(nums) - 1 while left <= right: middle = (left + right) // 2 if nums\[middle] == target: return middle if nums\[left] <= nums\[middle]: # \* left half is sorted if nums\[left] <= target < nums\[middle]: right = middle - 1 else: left = middle + 1 else: # \* right half is sorted if nums\[middle] < target <= nums\[right]: left = middle + 1 else: right = middle - 1 return -1 ```

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

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)

---

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

1. Comenzaríamos con dos apuntadores a los extremos.
   • i: Apuntador izquierdo, comienza en 0.
   • d: Apuntador derecho, comienza en len(s) - 1.
2. 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.

1. 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.
2. 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.