Algoritam nasumičnog pretraživanja (Random Search) u Java: Uvod, Kako radi, Primjer

Algoritam slučajnog pretraživanja, poznat i kao Monte Carlo pretraživanje, metoda je pretraživanja koja se temelji na slučajnosti. Umjesto uzastopne provjere svakog elementa u nizu podataka, ovaj algoritam nasumično odabire niz elemenata za ispitivanje. Ovaj pristup štedi vrijeme i resurse u usporedbi sa sekvencijalnim pretraživanjem.

Kako radi

1. Korak 1: Započnite s nizom podataka koji želite pretraživati.

2. Korak 2: Nasumično odaberite određeni broj elemenata za ispitivanje.

3. Korak 3: Provjerite odabrane elemente da vidite odgovaraju li uvjetu pretraživanja.

4. Korak 4: Ako je pronađen odgovarajući element, vratite rezultat; ako nije, vratite se na korak 2.

5. Korak 5: Nastavite s postupkom dok se ne pronađe podudaranje ili dok se ne dosegne najveći broj pokušaja.

Prednosti i nedostatci

Prednosti:

• Učinkovitost resursa: Štedi vrijeme i memoriju, posebno za velika polja podataka.
• Slučajnost: Nije lako predvidljivo, pogodno za situacije koje zahtijevaju slučajnost.

Nedostaci:

• Nema jamstva za uspjeh: Ne postoji jamstvo da će algoritam pronaći željeni rezultat.
• Može potrajati dugo: U najgorem slučaju, algoritam može potrajati dulje od sekvencijalnog pretraživanja.

Primjer i objašnjenje

Razmotrite sljedeći primjer korištenja algoritma nasumičnog pretraživanja za pronalaženje cijelog broja u nizu:

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.");  
        }  
    }  
}  

U ovom primjeru koristimo algoritam nasumičnog pretraživanja za pronalaženje cijelog broja u nizu. Iteriramo nizom, nasumično odabiremo indeks i provjeravamo odgovara li element na tom indeksu ciljnom broju. Ako se nađe, vraćamo indeks; ako ne, nastavljamo dok se ne postigne maksimalan broj pokušaja.