O que é uma matriz classificada girada?

Considere uma matriz ordenada, por exemplo:

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

Agora, se esse array for girado em algum pivô, digamos no índice 3, ele se tornaria:

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

Observe que o array ainda está classificado, mas está dividido em duas partes. Nosso objetivo é procurar um valor alvo em tais matrizes de forma eficiente.

A estratégia de pesquisa

Para pesquisar em um array ordenado rotacionado, precisamos:

1. Encontre o pivô: O pivô é o ponto onde a matriz faz a transição de valores maiores para valores menores.
2. Pesquisa binária: Assim que encontrarmos o pivô, podemos usar a pesquisa binária na metade apropriada do array.

Explicação passo a passo do código

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] 







  
  
  Explicação do Código




procurar():


Esta função é responsável por procurar o alvo na matriz ordenada girada.
Primeiro, encontramos o pivot usando a função searchPivot().
Dependendo da posição do pivô, decidimos então qual metade do array pesquisar usando a pesquisa binária.



binarySearch():


Um algoritmo de pesquisa binária padrão para encontrar o alvo em uma submatriz classificada.
Definimos os índices de início e fim e estreitamos progressivamente o espaço de pesquisa.



searchPivot():


Esta função identifica o ponto de pivô (o local onde a matriz gira).
O pivô é o índice onde a ordem de classificação é "quebrada" (ou seja, a matriz vai de um valor mais alto para um valor mais baixo).
Se nenhum pivô for encontrado, significa que o array não foi girado e podemos realizar uma pesquisa binária regular.








  
  
  Como funciona o algoritmo


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

• O pivô está no índice 2 (6 é o maior e é seguido por 1, o menor).
• Usamos esse pivô para dividir o array em duas partes: [4, 5, 6] e [1, 2, 3].
• Se o alvo for maior ou igual ao primeiro elemento (4 neste caso), buscamos a metade esquerda. Caso contrário, pesquisamos a metade direita.

Este método garante uma pesquisa eficiente, alcançando uma complexidade de tempo de O(log n), semelhante a uma pesquisa binária padrão.

Conclusão

Matrizes classificadas giradas são uma pergunta comum em entrevistas e um desafio útil para aprofundar sua compreensão da pesquisa binária. Ao encontrar o pivô e adaptar nossa pesquisa binária de acordo, podemos pesquisar com eficiência a matriz em tempo logarítmico.

Se você achou este artigo útil, sinta-se à vontade para se conectar comigo no LinkedIn ou compartilhar sua opinião nos comentários! Boa codificação!