Programando Search in Rotated Arrays

👨‍💻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 que ir escribiendo test unitarios para probar y tambien para practicar

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.

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

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