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

Programando Search in Rotated Arrays

30/35
Recursos

Aportes 13

Preguntas 1

Ordenar por:

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

👨‍💻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.

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

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

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.

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

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
}

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

Yo hago las pruebas con:

https://pythontutor.com/render.html#mode=display

No sé porque me imagine que de verdad se dividía el array en 2 cada vez, y no, pues es la gestión del índice que hace parecer que se divide la lista.


Comparto el código de la profe en Python

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

Solución en Python

class Solution:
    def find_inflexion_point(self, n_nums): 
        inflexion_point = len(n_nums) // 2 
        while True: 
            left, right = n_nums[0:inflexion_point], n_nums[inflexion_point:]
            if left[0] <= left[-1]:
                if right[0] <= right[-1]:
                    return inflexion_point
                else: 
                    inflexion_point += 1
            else: 
                inflexion_point -= 1
        return inflexion_point


    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 1: 
            if nums[0] == target:
                return 0
            else: 
                return -1
        else: 
            inflexion_point = self.find_inflexion_point(nums)
            
            moved_right_prior = 0
            while True: 
                left, right = nums[0: inflexion_point], nums[inflexion_point:]
                if left[0] == target: 
                    return moved_right_prior
                elif left[-1] == target: 
                    return moved_right_prior + len(left) - 1
                elif right[0] == target: 
                    moved_right_prior += len(left)
                    return moved_right_prior 
                elif right[-1] == target:
                    moved_right_prior += len(left)
                    return moved_right_prior + len(right) - 1 
                elif left[0] <= target and target <= left[-1]:
                    nums = left 
                    inflexion_point = len(left) // 2 
                elif right[0] <= target and target <= right[-1]:
                    nums = right
                    inflexion_point = len(right) // 2 
                    moved_right_prior += len(left)
                else: 
                    return -1
                
            
            
        return 0