Qu'est-ce qu'un tableau trié avec rotation ?

Considérons un tableau trié, par exemple :

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

Maintenant, si ce tableau subit une rotation à un certain pivot, disons à l'index 3, il deviendrait :

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

Remarquez que le tableau est toujours trié, mais il est divisé en deux parties. Notre objectif est de rechercher efficacement une valeur cible dans de tels tableaux.

La stratégie de recherche

Pour effectuer une recherche dans un tableau trié avec rotation, nous devons :

1. Trouver le pivot : le pivot est le point où le tableau passe de valeurs plus grandes à des valeurs plus petites.
2. Recherche binaire : une fois que nous avons trouvé le pivot, nous pouvons utiliser la recherche binaire sur la moitié appropriée du tableau.

Explication du code étape par étape

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] 





  
  
  Explication du Code



recherche():

Cette fonction est chargée de rechercher la cible dans le tableau trié pivoté.
Tout d'abord, nous trouvons le pivot à l'aide de la fonction searchPivot().
En fonction de la position du pivot, nous décidons ensuite dans quelle moitié du tableau rechercher en utilisant la recherche binaire.


binarySearch() :

Un algorithme de recherche binaire standard pour trouver la cible dans un sous-tableau trié.
Nous définissons les indices de début et de fin et réduisons progressivement l'espace de recherche.


searchPivot() :

Cette fonction identifie le point pivot (l'endroit où le tableau tourne).
Le pivot est l'index où l'ordre de tri est « rompu » (c'est-à-dire que le tableau passe d'une valeur supérieure à une valeur inférieure).
Si aucun pivot n'est trouvé, cela signifie que le tableau n'a pas été pivoté et nous pouvons effectuer une recherche binaire régulière.


  
  
  Comment fonctionne l'algorithme


Pour un tableau comme [4, 5, 6, 1, 2, 3] :

• Le pivot est à l'index 2 (6 est le plus grand, et il est suivi de 1, le plus petit).
• Nous utilisons ce pivot pour diviser le tableau en deux parties : [4, 5, 6] et [1, 2, 3].
• Si la cible est supérieure ou égale au premier élément (4 dans ce cas), on recherche la moitié gauche. Sinon, on cherche la moitié droite.

Cette méthode garantit que nous effectuons une recherche efficace, en atteignant une complexité temporelle de O(log n), similaire à une recherche binaire standard.

Conclusion

Les tableaux triés avec rotation sont une question d'entretien courante et un défi utile pour approfondir votre compréhension de la recherche binaire. En trouvant le pivot et en adaptant notre recherche binaire en conséquence, nous pouvons effectuer une recherche efficace dans le tableau en temps logarithmique.

Si vous avez trouvé cet article utile, n'hésitez pas à me contacter sur LinkedIn ou à partager vos réflexions dans les commentaires ! Bon codage !