¿Qué es una matriz ordenada rotada?

Considere una matriz ordenada, por ejemplo:

[1, 2, 3, 4, 5, 6]

Ahora, si esta matriz se gira en algún pivote, digamos en el índice 3, se convertiría en:

[4, 5, 6, 1, 2, 3]

Observe que la matriz todavía está ordenada, pero está dividida en dos partes. Nuestro objetivo es buscar un valor objetivo en dichas matrices de manera eficiente.

La estrategia de búsqueda

Para buscar en una matriz ordenada rotada, necesitamos:

1. Encontrar el pivote: El pivote es el punto donde la matriz pasa de valores más grandes a más pequeños.
2. Búsqueda binaria: una vez que encontramos el pivote, podemos usar la búsqueda binaria en la mitad apropiada de la matriz.

Explicación del código paso a paso

class Solution {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 1, 2, 3}; // Example of rotated sorted array
        int target = 5;

        // Searching for the target
        int result = search(arr, target);

        // Displaying the result
        System.out.println("Index of target: "   result);
    }

    // Main search function to find the target in a rotated sorted array
    public static int search(int[] nums, int target) {
        // Step 1: Find the pivot
        int pivot = searchPivot(nums);

        // Step 2: If no pivot, perform regular binary search
        if (pivot == -1) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }

        // Step 3: If the target is at the pivot, return the pivot index
        if (nums[pivot] == target) {
            return pivot;
        }

        // Step 4: Decide which half of the array to search
        if (target >= nums[0]) {
            return binarySearch(nums, target, 0, pivot - 1); // Search left side
        } else {
            return binarySearch(nums, target, pivot   1, nums.length - 1); // Search right side
        }
    }

    // Binary search helper function
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start  arr[mid   1]) {
                return mid;
            }

            // Check if the pivot is before the mid
            if (mid > start && arr[mid] 





  
  
  Explicación del Código



buscar():

Esta función es responsable de buscar el objetivo en la matriz ordenada rotada.
Primero, encontramos el pivote usando la función searchPivot().
Dependiendo de la posición del pivote, decidimos en qué mitad de la matriz buscar mediante la búsqueda binaria.


búsqueda binaria():

Un algoritmo de búsqueda binaria estándar para encontrar el objetivo en una submatriz ordenada.
Definimos los índices de inicio y fin y acotamos progresivamente el espacio de búsqueda.


Pivote de búsqueda():

Esta función identifica el punto de pivote (el lugar donde gira la matriz).
El pivote es el índice donde el orden de clasificación se "rompe" (es decir, la matriz pasa de un valor superior a un valor inferior).
Si no se encuentra ningún pivote, significa que la matriz no se giró y podemos realizar una búsqueda binaria normal.


  
  
  Cómo funciona el algoritmo


Para una matriz como [4, 5, 6, 1, 2, 3]:

• El pivote está en el índice 2 (6 es el más grande y le sigue 1, el más pequeño).
• Usamos este pivote para dividir la matriz en dos partes: [4, 5, 6] y [1, 2, 3].
• Si el objetivo es mayor o igual que el primer elemento (4 en este caso), buscamos en la mitad izquierda. En caso contrario, buscamos la mitad derecha.

Este método garantiza que busquemos de manera eficiente, logrando una complejidad temporal de O(log n), similar a una búsqueda binaria estándar.

Conclusión

Las matrices ordenadas rotadas son una pregunta común en las entrevistas y un desafío útil para profundizar su comprensión de la búsqueda binaria. Al encontrar el pivote y adaptar nuestra búsqueda binaria en consecuencia, podemos buscar eficientemente a través de la matriz en tiempo logarítmico.

Si este artículo te resultó útil, no dudes en conectarte conmigo en LinkedIn o compartir tus ideas en los comentarios. ¡Feliz codificación!