Recherche d'un élément dans un tableau infini à l'aide de Java

Énoncé du problème

Étant donné un tableau infini d'entiers triés, nous devons trouver l'index d'un nombre cible donné. Le tableau est « infini », ce qui signifie que nous ne pouvons pas déterminer sa taille à l’avance, nous ne pouvons donc pas simplement appliquer directement une recherche binaire traditionnelle.

Aperçu de l’approche

1. Commencez avec une petite plage : Dans un premier temps, supposons que l'élément se situe dans une petite plage (par exemple, entre les indices 0 et 1).

2. Augmenter dynamiquement la plage : Si l'élément cible n'est pas trouvé dans la plage initiale, nous doublons la taille de la plage pour chercher plus loin. Cette croissance exponentielle nous permet de cibler rapidement la plage où pourrait se situer la cible.

3. Recherche binaire dans la plage : Une fois que nous avons déterminé une plage appropriée contenant la cible, nous appliquons la recherche binaire pour trouver efficacement l'index de la cible.

Le code

public class InfiniteArraySearch {
    public static void main(String[] args) {
        // Define the array (for demonstration purposes, treat this as infinite)
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};  
        int target = 6;

        // Call the function to find the target element
        int result = findElementInInfiniteArray(arr, target);
        System.out.println("Element found at index: " + result);
    }

    // Function to find the target in the infinite array
    static int findElementInInfiniteArray(int[] arr, int target) {
        // Start with a small range
        int start = 0;
        int end = 1;

        // Dynamically increase the range until the target is within bounds
        while (target > arr[end]) {
            int newStart = end + 1;  // Update start to one after the current end
            end = end + (end - start + 1) * 2;  // Double the range
            start = newStart;  // Move the start to newStart
        }

        // Perform binary search within the determined range
        return binarySearch(arr, target, start, end);
    }

    // Standard binary search implementation
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (target < arr[mid]) {
                end = mid - 1;  // Move the end to the left
            } else if (target > arr[mid]) {
                start = mid + 1;  // Move the start to the right
            } else {
                return mid;  // Element found
            }
        }
        return -1;  // Element not found
    }
}

Explication du Code

1. Fonction principale

La fonction main définit un exemple de tableau arr et une valeur cible 6. Pour plus de simplicité, nous supposons ici que le tableau est fini, mais conceptuellement, nous le traitons comme infini. La fonction principale appelle ensuite findElementInInfiniteArray pour rechercher la cible et imprime l'index s'il est trouvé.

2. Extension de la plage (extension linéaire de la zone de recherche)

Dans la méthode findElementInInfiniteArray :

• Nous commençons par supposer que l'élément se situe dans la plage [0, 1].
• Si la cible est supérieure à la valeur à arr[end], cela signifie que la cible n'est pas dans la plage actuelle. Ainsi, nous élargissons la plage de manière exponentielle en la doublant (fin = fin + (fin - début + 1) * 2). Cela nous permet effectivement de couvrir plus de terrain à chaque itération.

3. Recherche binaire

Une fois que nous savons que la cible doit se situer entre le début et la fin, nous effectuons une recherche binaire standard. La recherche binaire est un moyen efficace de rechercher dans des tableaux triés, car elle réduit l'espace de recherche de moitié à chaque étape. Les comparaisons clés sont :

• Si la cible est inférieure à l'élément du milieu (arr[mid]), recherchez la moitié gauche.
• Si la cible est plus grande, recherchez la moitié droite.
• Si la cible correspond à l'élément du milieu, renvoie son index.

4. Cas Edge

• Si la cible est plus petite que le plus petit élément du tableau, ou si le tableau ne contient pas du tout la cible, l'algorithme renverra -1.

Complexité temporelle

1. Extension de la plage : La plage double à chaque itération, il faut donc des opérations O(log N) pour trouver la bonne plage où se trouve la cible.

2. Recherche binaire : Une fois la plage trouvée, la recherche binaire s'exécute en O (log M), où M est la taille de la plage.

Ainsi, la complexité temporelle globale est d'environ O(log N + log M).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!