(Random Search) Algoritem naključnega iskanja v Java: uvod, kako deluje, primer

Algoritem naključnega iskanja, znan tudi kot iskanje po Monte Carlu, je metoda iskanja, ki temelji na naključnosti. Namesto zaporednega preverjanja vsakega elementa v podatkovnem nizu ta algoritem naključno izbere več elementov za pregled. Ta pristop prihrani čas in sredstva v primerjavi z zaporednim iskanjem.

Kako deluje

1. 1. korak: Začnite s podatkovnim nizom, ki ga želite iskati.

2. 2. korak: Naključno izberite določeno število elementov za pregled.

3. 3. korak: Preverite izbrane elemente, ali se ujemajo z iskalnim pogojem.

4. 4. korak: Če je najden ujemajoči se element, vrni rezultat; če ne, se vrnite na 2. korak.

5. 5. korak: Nadaljujte s postopkom, dokler ni ujemanje ali doseženo največje število poskusov.

Prednosti in slabosti

Prednosti:

• Učinkovita poraba virov: prihrani čas in pomnilnik, zlasti pri velikih podatkovnih nizih.
• Naključnost: Ni lahko predvidljivo, primerno za situacije, ki zahtevajo naključnost.

Slabosti:

• Ni zagotovila za uspeh: Ni zagotovila, da bo algoritem našel želeni rezultat.
• Lahko traja dolgo časa: v najslabšem primeru lahko algoritem traja dlje kot zaporedno iskanje.

Primer in razlaga

Razmislite o naslednjem primeru uporabe algoritma naključnega iskanja za iskanje celega števila v matriki:

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

V tem primeru uporabljamo algoritem naključnega iskanja za iskanje celega števila v matriki. Iteriramo po matriki, naključno izberemo indeks in preverimo, ali se element na tem indeksu ujema s ciljno številko. Če najdemo, vrnemo indeks; če ne, nadaljujemo, dokler ne dosežemo največjega števila poskusov.