Algorithme de recherche aléatoire (Random Search) dans Java  : Introduction, comment ça marche, exemple

L'algorithme de recherche aléatoire, également connu sous le nom de recherche Monte Carlo, est une méthode de recherche basée sur le caractère aléatoire. Au lieu de vérifier séquentiellement chaque élément d’un tableau de données, cet algorithme sélectionne au hasard un certain nombre d’éléments à examiner. Cette approche permet d'économiser du temps et des ressources par rapport à la recherche séquentielle.

Comment ça fonctionne

1. Étape 1 : Commencez par le tableau de données que vous souhaitez rechercher.

2. Étape 2: Sélectionnez aléatoirement un certain nombre d’éléments à examiner.

3. Étape 3: Vérifiez les éléments sélectionnés pour voir s'ils correspondent à la condition de recherche.

4. Étape 4: Si un élément correspondant est trouvé, renvoyez le résultat ; sinon, revenez à l’étape 2.

5. Étape 5 : Continuez le processus jusqu'à ce qu'une correspondance soit trouvée ou que le nombre maximum de tentatives soit atteint.

Avantages et inconvénients

Avantages:

• Efficacité en ressources : permet d'économiser du temps et de la mémoire, en particulier pour les grandes baies de données.
• Caractère aléatoire : difficilement prévisible, adapté aux situations nécessitant du hasard.

Désavantages:

• Aucune garantie de succès : rien ne garantit que l'algorithme trouvera le résultat souhaité.
• Peut prendre beaucoup de temps : dans le pire des cas, l'algorithme peut prendre plus de temps qu'une recherche séquentielle.

Exemple et explication

Prenons l'exemple suivant d'utilisation de l'algorithme de recherche aléatoire pour rechercher un entier dans un tableau :

import java.util.Random;  
  
public class RandomSearchExample {  
    static int randomSearch(int[] arr, int target) {  
        Random rand = new Random();  
        int maxAttempts = arr.length; // Maximum number of attempts  
        for(int i = 0; i < maxAttempts; i++) {  
            int randomIndex = rand.nextInt(arr.length); // Randomly select an index  
            if(arr[randomIndex] == target) {  
                return randomIndex; // Return the index if found  
            }  
        }  
        return -1; // Return -1 if not found  
    }  
  
    public static void main(String[] args) {  
        int[] numbers = {1, 5, 9, 3, 7};  
        int target = 3;  
        int result = randomSearch(numbers, target);  
        if(result != -1) {  
            System.out.println("Number " + target + " found at index " + result);  
        } else {  
            System.out.println("Number " + target + " not found in the array.");  
        }  
    }  
}  

Dans cet exemple, nous utilisons l'algorithme de recherche aléatoire pour trouver un entier dans un tableau. Nous parcourons le tableau, sélectionnons au hasard un index et vérifions si l'élément à cet index correspond au numéro cible. S'il est trouvé, nous renvoyons l'index ; sinon, on continue jusqu'à ce que le nombre maximum de tentatives soit atteint.