Introducción

1

Arrays y Strings para resolver algoritmos avanzados

2

Arrays y Strings en detalle

Dos Apuntadores

3

Patrón de Dos Apuntadores

4

Verifying Alien Dictionary: análisis del problema

5

Solución de Verifying Alien Dictionary

6

Playground: Verifying Alien Dictionary

7

Programando Verifying Alien Dictionary con JavaScript

8

Merge Two Sorted Lists: análisis del problema

9

Solución de Merge Two Sorted Lists

10

Playground: Merge Two Sorted Lists

11

Programando Merge Two Sorted Lists con Python

12

Container With Most Water: análisis del problema

13

Solución de Container With Most Water

14

Playground: Container with Most Water

15

Programando Container With Most Water con Java

16

Reto: Trapping Rain Water

17

Ejercicios recomendados de Dos Apuntadores

18

Ejercicios resueltos de Dos Apuntadores

Ventana Deslizante

19

Patrón de Ventana Deslizante

20

Longest Substring Without Repeating Characters: análisis del problema

21

Solución de Longest Substring Without Repeating Characters

22

Playground: Longest Substring Without Repeating Characters

23

Programando Longest Substring Without Repeating Characters con Python

24

Ejercicios recomendados de Ventana Deslizante

25

Ejercicios resueltos de Ventana Deslizante

Búsqueda Binaria

26

Algoritmo de Búsqueda Binaria

27

Search in Rotated Arrays: análisis del problema

28

Solución de Search in Rotated Arrays

29

Playground: Search in Rotated Arrays

30

Programando Search in Rotated Arrays

31

Search 2D Array Matrix: análisis del problema

32

Solución de Search 2D Array Matrix

33

Playground: Search 2D Array Matrix

34

Programando Search 2D Array Matrix

Próximos pasos

35

Toma el Curso Avanzado de Algoritmos: Estructuras de Datos Lineales

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Aprende Inglés, Programación, AI, Ciberseguridad y mucho más.

Antes: $249

Currency
$209
Suscríbete

Termina en:

3 Días
19 Hrs
16 Min
17 Seg

Search in Rotated Arrays: análisis del problema

27/35
Recursos

Aportes 3

Preguntas 0

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

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.