Categorías
Algorithms Interview

LeetCode – Búsqueda en matriz ordenada rotada (Java)

Suponga que una matriz ordenada se gira en algún pivote desconocido para usted de antemano. (es decir, 0 1 2 4 5 6 7 podría convertirse en 4 5 6 7 0 1 2).

Se le da un valor objetivo para buscar. Si se encuentra en la matriz, devuelve su índice; de ​​lo contrario, devuelve -1. Puede asumir que no existe ningún duplicado en la matriz.

Análisis

Para utilizar la búsqueda binaria en la matriz ordenada rotada, necesitamos determinar cómo actualizar los punteros izquierdo y derecho. Hay dos casos principales, como se muestra a continuación:

Una vez que se identifican los dos casos, el problema es sencillo de resolver. Solo necesitamos verificar si el elemento de destino está en el lado ordenado y, en función de eso, mover los punteros hacia la izquierda o hacia la derecha.

Solución Java 1- Recusiva

public int search(int[] nums, int target) {
    return binarySearch(nums, 0, nums.length-1, target);
}
 
public int binarySearch(int[] nums, int left, int right, int target){
    if(left>right) 
        return -1;
 
    int mid = left + (right-left)/2;
 
    if(target == nums[mid])
        return mid;
 
    if(nums[left] <= nums[mid]){
        if(nums[left]<=target && target<nums[mid]){
          return binarySearch(nums,left, mid-1, target);
        }else{
          return  binarySearch(nums, mid+1, right, target);
        }
    }else {
        if(nums[mid]<target&& target<=nums[right]){
          return  binarySearch(nums,mid+1, right, target);
        }else{
          return  binarySearch(nums, left, mid-1, target);
        }
    }
}
  LeetCode - Particionamiento Palindrome (Java)

Solución Java 2: iterativa

public int search(int[] nums, int target) {
    int left = 0;
    int right= nums.length-1;
 
    while(left<=right){
        int mid = left + (right-left)/2;
        if(target==nums[mid])
            return mid;
 
        if(nums[left]<=nums[mid]){
            if(nums[left]<=target&& target<nums[mid]){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }else{
            if(nums[mid]<target&& target<=nums[right]){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }    
    }
 
    return -1;
}

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *